二叉树的前、中、后序遍历(C++)
二叉树的前、中、后序遍历(C++)
二叉树的遍历是数据结构与算法中的基础内容,掌握前序、中序和后序遍历方法对于深入学习树结构及其算法至关重要。本文通过代码示例介绍了二叉树的三种深度优先遍历方法,并使用递归方式实现,帮助读者深入理解二叉树的遍历过程及其应用。
1 简介
本文通过代码示例介绍了二叉树的三种深度优先遍历方法——前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根),并使用递归方式实现。递归方法直观易懂,符合树的天然递归结构,每种遍历方式都遵循固定的访问顺序:前序遍历先访问根节点,再遍历左子树和右子树;中序遍历先遍历左子树,再访问根节点,最后遍历右子树;后序遍历则先遍历左右子树,最后访问根节点。本文提供清晰的 C++ 代码示例,并分析递归的工作原理,帮助读者深入理解二叉树的遍历过程及其应用。
2 前序遍历
2.1 问题描述
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
数据范围:二叉树的节点数量满足 1≤n≤100 1≤n≤100 ,二叉树节点的值满足 1≤val≤100 1≤val≤100 ,树的各节点的值各不相同
示例 1:
2.1.1 示例1
输入:
{1,#,2,3}
返回值:
[1,2,3]
2.2 解题思路
采用递归方式实现二叉树的前序遍历(根-左-右),并将遍历结果存储在
vector
中。
preorderTraversal
函数调用
preorder
递归函数,
preorder
依次执行:访问当前节点(存入
result
)→ 遍历左子树 → 遍历右子树。递归终止条件是当前节点为空(即
nullptr
),此时直接返回。
2.3 代码实现
vector<int> preorderTraversal(TreeNode* root) {
// write code here
vector<int> result;
preorder(root, result);
return result;
}
void preorder(TreeNode* node, vector<int>& result)
{
if(node == nullptr) return;
result.push_back(node->val);
preorder(node->left, result);
preorder(node->right, result);
}
3 中序遍历
3.1 问题描述
给定一个二叉树的根节点root,返回它的中序遍历结果。
数据范围:树上节点数满足 0≤n≤10000≤n≤1000,树上每个节点的值满足 −1000≤val≤1000−1000≤val≤1000
进阶:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
3.1.1 示例1
输入:
{1,2,#,#,3}
返回值:[2,3,1]
3.1.2 示例2
输入:
{}
返回值:[]
3.1.3 示例3
输入:
{1,2}
返回值:[2,1]
3.1.4 示例4
输入:
{1,#,2}
返回值:[1,2]
3.2 解题思路
采用递归方式实现二叉树的中序遍历(左-根-右),并将遍历结果存储在
vector
中。
inorderTraversal
函数调用
inorder
递归函数,
inorder
依次执行:先递归遍历左子树 → 访问当前节点(存入
result
)→ 递归遍历右子树。递归终止条件是当前节点为空(即
nullptr
),此时直接返回。
3.3 代码实现
vector<int> inorderTraversal(TreeNode* root) {
// write code here
vector<int> result;
inorder(root, result);
return result;
}
void inorder(TreeNode* node, vector<int>& result)
{
if(node == nullptr) return;
inorder(node->left, result);
result.push_back(node->val);
inorder(node->right, result);
}
4 后序遍历
4.1 问题描述
给定一个二叉树,返回他的后序遍历的序列。
后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。
数据范围:二叉树的节点数量满足 1≤n≤100 1≤n≤100 ,二叉树节点的值满足 1≤val≤100 1≤val≤100 ,树的各节点的值各不相同
样例图
4.1.1 示例1
输入:
{1,#,2,3}
返回值:
[3,2,1]
4.1.2 示例2
输入:
{1}
返回值:
[1]
4.2 解题思路
采用递归方式实现二叉树的后序遍历(左-右-根),并将遍历结果存储在
vector
中。
postorderTraversal
函数调用
postorder
递归函数,
postorder
依次执行:先递归遍历左子树 → 递归遍历右子树 → 访问当前节点(存入
result
)。递归终止条件是当前节点为空(即
nullptr
),此时直接返回。
4.3 代码实现
vector<int> postorderTraversal(TreeNode* root) {
// write code here
vector<int> result;
postorder(root, result);
return result;
}
void postorder(TreeNode* node, vector<int>& result)
{
if(node == nullptr) return;
postorder(node->left, result);
postorder(node->right, result);
result.push_back(node->val);
}
5 总结
本文介绍了二叉树的前序遍历(根-左-右)、中序遍历(左-根-右)和后序遍历(左-右-根)三种深度优先遍历方法,并使用递归方式分别实现。递归方法利用二叉树的天然递归结构,使代码简洁直观,每种遍历方式都遵循固定的访问顺序。文章通过示例输入输出、解题思路解析和代码实现,帮助读者掌握不同遍历方法的应用。递归终止条件为当前节点为空(nullptr),以确保遍历完整执行。理解这三种遍历方式对于深入学习树结构及其算法至关重要,能够为后续的二叉树问题提供坚实基础。