目录
二叉树的遍历
前序遍历
中序遍历
后序遍历
层序遍历
二叉树基础OJ题
单值二叉树
检查两颗树是否相同
对称二叉树
二叉树的前序遍历
二叉树的后序遍历
二叉树中序遍历
另一颗树的子树
二叉树的遍历
二叉树有四种主要的遍历方式：
前序遍历（Preorder Traversal）：访问顺序为根节点 -> 左子树 -> 右子树。递归公式通常表示为：root, left, right。
中序遍历（Inorder Traversal）：访问顺序为左子树 -> 根节点 -> 右子树。递归公式为：left, root, right。
后序遍历（Postorder Traversal）：访问顺序为左子树 -> 右子树 -> 根节点。递归公式为：left, right, root。
层序遍历（Level Order Traversal）：从上到下、从左到右访问每一层的节点。这是唯一一种广度优先遍历策略，而非深度优先。
前序遍历
二叉树的前序遍历顺序是：根 → 左子树 → 右子树，非递归遍历二叉树时，利用栈能有效模拟前序遍历（根-左-右）过程：先将所有左节点压栈并访问，随后逐个弹出栈顶节点并处理其右子树，以此循环直至栈空，完成整个树的遍历。
具体步骤如下：
- 将左路结点入栈，入栈的同时访问左路结点。
- 取出栈顶结点top。
- 准备访问top结点的右子树。
代码实现如下：
struct TreeNode
{
int val; // 节点的值
TreeNode* left; // 指向左子节点的指针
TreeNode* right; // 指向右子节点的指针
// 构造函数
TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默认构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 带值构造函数
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} // 带左右子节点的构造函数
};
class Solution
{
public:
// 前序遍历函数，输入为二叉树的根节点，返回遍历结果的值组成的vector
vector preorderTraversal(TreeNode* root)
{
stack st; // 使用栈存储待访问的节点
vector ret; // 用于存储遍历结果
// 初始化当前访问节点为根节点
TreeNode* cur = root;
// 当当前节点非空或栈非空时继续遍历
while (cur || !st.empty())
{
// 遍历到最左侧的节点，沿途压栈并记录节点值
while (cur)
{
st.push(cur); // 当前节点入栈
ret.push_back(cur->val); // 记录节点值
cur = cur->left; // 移动到当前节点的左子节点
}
// 当左子树遍历完后，访问栈顶节点的右子树
TreeNode* top = st.top(); // 获取栈顶节点
st.pop(); // 栈顶节点出栈（已访问）
cur = top->right; // 移动到栈顶节点的右子节点继续遍历
}
return ret; // 返回前序遍历的结果
}
};
中序遍历
二叉树的中序遍历顺序是：左子树 → 根 → 右子树，我们可以先将二叉树的左路结点入栈，当左路结点入栈完毕后，再从栈顶依次取出结点，在取出结点的同时便对其进行访问，此时就相当于先访问了左子树再访问了根，之后再用同样的方式访问取出结点的右子树即可。
具体步骤如下：
- 将左路结点入栈。
- 取出栈顶结点top并访问。
- 准备访问top结点的右子树。
代码实现如下：
struct TreeNode
{
int val; // 节点的值
TreeNode* left; // 指向左子节点的指针
TreeNode* right; // 指向右子节点的指针
// 构造函数
TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默认构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 带值构造函数
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} // 带左右子节点的构造函数
};
class Solution
{
public:
// 中序遍历函数，输入为二叉树的根节点，返回中序遍历结果的值组成的vector
vector inorderTraversal(TreeNode* root)
{
stack st; // 使用栈辅助遍历过程
vector ret; // 存储遍历结果
// 初始化当前访问节点为根节点
TreeNode* cur = root;
// 当当前节点非空或栈非空时，继续遍历
while (cur != nullptr || !st.empty())
{
// 1. 遍历到最左侧的节点，沿途将非空的左子节点压入栈中
while (cur != nullptr)
{
st.push(cur);
cur = cur->left; // 移动到当前节点的左子节点
}
// 2. 取出栈顶节点（当前节点的左子树已经遍历完成），访问该节点，并将其值存入结果vector
TreeNode* top = st.top();
st.pop();
ret.push_back(top->val);
// 3. 准备访问当前节点的右子树
cur = top->right; // 移动到当前节点的右子节点
}
return ret; // 完成遍历后，返回中序遍历的结果vector
}
};
后序遍历
二叉树的后序遍历顺序是：左子树 → 右子树 → 根，我们可以先将二叉树的左路结点入栈，当左路结点入栈完毕后，再观察栈顶结点，若栈顶结点的右子树为空，或栈顶结点的右子树已经被访问过了，则栈顶结点可以出栈并访问，若栈顶结点的右子树还未被访问，则用同样的方式访问栈顶结点的右子树，直到其右子树被访问后再访问该结点，这时的访问顺序遵循了二叉树的后序遍历所要求的顺序。
具体步骤如下：
- 将左路结点入栈。
- 观察栈顶结点top。
- 若top结点的右子树为空，或top结点的右子树已经访问过了，则访问top结点。访问top结点后将其从栈中弹出，并更新上一次访问的结点为top。
- 若top结点的右子树还未被访问，则准备访问其右子树。
代码实现如下：
struct TreeNode
{
int val; // 节点的值
TreeNode* left; // 指向左子节点的指针
TreeNode* right; // 指向右子节点的指针
// 构造函数
TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默认构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 带值构造函数
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} // 带左右子节点的构造函数
};
class Solution
{
public:
// 后序遍历函数，输入为二叉树的根节点，返回后序遍历结果的值组成的vector
vector postorderTraversal(TreeNode* root)
{
stack st; // 辅助栈，用来存储待访问的节点
vector ret; // 用于存放后序遍历的结果
TreeNode* cur = root; // 当前访问的节点，初始化为根节点
TreeNode* prev = nullptr; // 上一个访问过的节点，初始为nullptr
// 当当前节点非空或栈非空时，继续遍历
while (cur != nullptr || !st.empty())
{
// 1. 一直向左走到尽头，将路径上的节点压入栈中
while (cur != nullptr)
{
st.push(cur);
cur = cur->left;
}
// 2. 取出栈顶节点
TreeNode* top = st.top();
// 3. 如果当前节点的右子树为空，或者右子树已经被访问过了（由prev标记）
// 则可以访问当前节点，然后将其从栈中弹出，转向下一个节点（即其父节点）
if (top->right == nullptr || top->right == prev)
{
st.pop(); // 弹出当前节点
ret.push_back(top->val); // 访问当前节点
prev = top; // 更新上一个访问的节点为当前节点
cur = nullptr; // 重置cur，以便下一轮循环从栈顶获取新节点
}
else
{ // 4. 如果右子树还没访问，则转向右子树
cur = top->right;
}
}
return ret; // 完成遍历后，返回后序遍历的结果vector
}
};
层序遍历
二叉树的层序遍历顺序是按照从上至下、从左至右的层次顺序访问每个节点。实现层序遍历的迭代方法主要依赖于队列（queue）数据结构。
具体步骤如下：
初始化: 创建一个空队列，并将二叉树的根节点（如果非空）放入队列中。同时，创建一个容器（如vector）用于存储遍历结果的每一层节点值。
循环处理: 当队列非空时，执行以下操作：
- 出队: 从队列中取出一个节点（称为当前节点），并将它的值添加到结果容器的当前层节点值列表中。
- 入队子节点: 将当前节点的左右子节点（如果存在）依次放入队列中。注意保持先左后右的顺序，以维持层次遍历的顺序。
- 结束当前层: 当当前层的所有节点都已被处理（即当前层的节点都已出队且它们的子节点已入队），则在结果容器中开始新的一层节点值列表。
重复步骤2：直到队列变空。每次完成一层的处理，实际上是在结果容器中增加了一个新的子vector，其中包含了该层所有节点的值。
代码实现如下：
struct TreeNode
{
int val; // 节点的值
TreeNode* left; // 指向左子节点的指针
TreeNode* right; // 指向右子节点的指针
// 构造函数
TreeNode() : val(0), left(nullptr), right(nullptr) {} // 默认构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 带值构造函数
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} // 带左右子节点的构造函数
};
class Solution
{
public:
// 层序遍历函数，输入为二叉树的根节点，返回层序遍历结果
vector> levelOrder(TreeNode* root)
{
vector> ret; // 最终返回的结果，存储每层节点的值
if (root == nullptr) return ret; // 空树情况，直接返回空结果
queue q; // 辅助队列，用来存储每一层的节点
q.push(root); // 将根节点入队
while (!q.empty())
{
int levelSize = q.size(); // 当前层的节点数量
vector levelNodes; // 用于存储当前层节点的值
// 遍历当前层的每一个节点
for (int i = 0; i < levelSize; ++i)
{
TreeNode* node = q.front(); // 取出队首节点
q.pop(); // 队首节点出队
levelNodes.push_back(node->val); // 记录节点值
// 将当前节点的左右子节点（如果存在）加入队列，以便下一层的遍历
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
// 当前层遍历完成后，将当前层的节点值加入最终结果
ret.push_back(levelNodes);
}
return ret; // 完成所有层的遍历后，返回结果
}
};
二叉树基础OJ题
单值二叉树-来源
题目描述：
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例：
代码：
class Solution
{
public:
// 定义一个公共成员函数isUnivalTree，接受一个指向二叉树根节点的指针作为参数
bool isUnivalTree(TreeNode* root)
{
// 如果根节点为空，认为它是单值树（空树可以视为所有节点值相同的一种特殊情况）
if(root == nullptr)
{
return true;
}
// 检查左子树：如果存在左子节点且其值不等于根节点的值，则返回false，表示不是单值树
if( root->left && root->left->val != root->val)
{
return false;
}
// 检查右子树：如果存在右子节点且其值不等于根节点的值，则返回false，表示不是单值树
if( root->right && root->right->val != root->val)
{
return false;
}
// 递归检查左子树和右子树是否也都是单值树。只有当左右子树都是单值树且它们的值与根节点相同，整棵树才是单值树。
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
};
检查两颗树是否相同-来源
题目描述：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例：
代码：
class Solution
{
public:
// 定义一个公共成员函数isSameTree，接受两个指向二叉树根节点的指针作为参数
bool isSameTree(TreeNode* p, TreeNode* q)
{
// 如果p和q都为nullptr，表示两个子树都是空树，因此它们相同
if (p == nullptr && q == nullptr)
{
return true;
}
// 如果只有一个为空，另一个非空，说明两棵树结构不同
else if (p == nullptr || q == nullptr)
{
return false;
}
// 如果当前节点的值不同，两棵树也不相同
else if (p->val != q->val)
{
return false;
}
// 如果以上情况都不满足，继续递归比较左右子树
else
{
// 同时递归检查左子树和右子树是否相同
// 只有当左右子树均相同，整个树才相同
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
};
对称二叉树-来源
题目描述：
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例：
代码：
class Solution
{
public:
// 辅助函数check，用于递归地比较二叉树的对称性
// 接受两个TreeNode指针，分别代表原树中的两个节点（用于比较）
bool check(TreeNode *p, TreeNode *q)
{
// 如果p和q都为nullptr，表示当前层的左右节点都已检查过且匹配，继续向上返回true
if (!p && !q)
return true;
// 如果p和q中只有一个为nullptr，说明左右子树节点数量不对称，返回false
if (!p || !q)
return false;
// 检查当前节点值是否相等，并递归检查“左子树的左节点”与“右子树的右节点”，
// 以及“左子树的右节点”与“右子树的左节点”是否对称
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
// 主函数isSymmetric，接收二叉树的根节点，调用check函数来判断整棵树是否对称
// 传入根节点两次作为check的参数，初始时比较的是根节点的左子树和右子树
bool isSymmetric(TreeNode* root)
{
return check(root, root);
}
};
二叉树的前序遍历-来源
题目描述：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例：
代码：
class Solution
{
public:
// 前序遍历的辅助函数，采用递归方式实现
// 参数root为当前访问的节点，res为存储遍历结果的向量
void preorder(TreeNode *root, vector &res)
{
// 如果当前节点为空，则直接返回，结束本次递归
if (root == nullptr)
{
return;
}
// 遍历顺序：先访问当前节点，将其值存入结果向量res
res.push_back(root->val);
// 递归遍历左子树
preorder(root->left, res);
// 递归遍历右子树
preorder(root->right, res);
}
// 主函数，用于执行二叉树的前序遍历并返回遍历结果
// 创建一个空向量res，调用preorder函数开始遍历
vector preorderTraversal(TreeNode *root)
{
vector res;
preorder(root, res);
return res; // 返回存储了前序遍历结果的向量
}
};
二叉树的中序遍历-来源
题目描述：
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例：
代码：
class Solution
{
public:
// 中序遍历的辅助函数，采用递归方式实现
// 参数root为当前访问的节点，res为存储遍历结果的向量
void inorder(TreeNode* root, vector& res)
{
// 如果当前节点为空，则直接返回，结束本次递归
if (!root)
{
return;
}
// 递归遍历左子树
inorder(root->left, res);
// 遍历顺序：访问当前节点，将其值添加到结果向量res中
res.push_back(root->val);
// 递归遍历右子树
inorder(root->right, res);
}
// 主函数，执行二叉树的中序遍历并返回遍历结果
// 初始化一个空向量res，调用inorder函数开始遍历
vector inorderTraversal(TreeNode* root)
{
vector res;
inorder(root, res);
return res; // 返回存储了中序遍历结果的向量
}
};
二叉树的后序遍历-来源
题目描述：
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例：
代码：
class Solution
{
public:
// 后序遍历的辅助函数，采用递归方式实现
// 参数root为当前访问的节点，res为存储遍历结果的向量
void postorder(TreeNode *root, vector &res)
{
// 如果当前节点为空，则直接返回，结束本次递归
if (root == nullptr)
{
return;
}
// 递归遍历左子树
postorder(root->left, res);
// 递归遍历右子树
postorder(root->right, res);
// 遍历顺序：先遍历左右子树，最后访问当前节点，并将其值添加到结果向量res中
res.push_back(root->val);
}
// 主函数，执行二叉树的后序遍历并返回遍历结果
// 初始化一个空向量res，调用postorder函数开始遍历
vector postorderTraversal(TreeNode *root)
{
vector res;
postorder(root, res);
return res; // 返回存储了后序遍历结果的向量
}
};
另一颗树的子树-来源
题目描述：
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例：
代码：
class Solution
{
public:
// 辅助函数check，用于比较两棵树的结构及节点值是否完全相同
// o和t分别是待比较的两个树的根节点
bool check(TreeNode *o, TreeNode *t)
{
// 如果o和t都为空，说明当前子树比较完毕且相同，返回true
if (!o && !t)
{
return true;
}
// 如果o和t其中一个为空，或者它们的值不同，说明不相同，返回false
if ((o && !t) || (!o && t) || (o->val != t->val))
{
return false;
}
// 递归比较左右子树
return check(o->left, t->left) && check(o->right, t->right);
}
// 深度优先搜索辅助函数dfs，用于在树s中查找是否存在和树t相同的子树
// o是树s中的当前节点，t是待查找的子树的根节点
bool dfs(TreeNode *o, TreeNode *t)
{
// 如果当前节点o为空，说明没有找到匹配的子树，返回false
if (!o)
{
return false;
}
// 检查当前节点o为根的子树是否与t相同，或在其左子树、右子树中寻找
return check(o, t) || dfs(o->left, t) || dfs(o->right, t);
}
// 主函数isSubtree，接收两棵树的根节点s和t，判断s中是否包含t作为子树
// 直接调用dfs函数进行深度优先搜索
bool isSubtree(TreeNode *s, TreeNode *t)
{
return dfs(s, t);
}
};
![[工业自动化-1]：PLC架构与工作原理](https://img-blog.csdnimg.cn/ce10a1471ed14382bc58364cf8bd5209.png)
还没有评论，来说两句吧...