C++算法训练营 Day13二叉树专题（1）
必备知识：
1.二叉树理论基础
2.二叉树的递归遍历
1. 二叉树的前序遍历
给你二叉树的根节点root，返回它节点值的前序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
- 解题思路：
前序遍历的顺序是：根节点 -> 左子树 -> 右子树。这个递归算法通过深度优先搜索(DFS)实现前序遍历。
递归过程：
访问根节点：将当前节点值加入结果列表
遍历左子树：递归处理左子节点
遍历右子树：递归处理右子节点
完整代码如下：
class Solution {
public:void traversal(TreeNode* cur, vector<int>& res) {// 1.递归终止条件：当前节点为空if (cur == nullptr) return;// 2.访问根节点（前序遍历的核心操作）res.push_back(cur->val); // 将当前节点值加入结果数组// 3.递归遍历左子树traversal(cur->left, res);// 4.递归遍历右子树traversal(cur->right, res);}//主函数：二叉树的前序遍历vector<int> preorderTraversal(TreeNode* root) {vector<int> result; //创建结果数组traversal(root, result); //调用递归函数return result; //返回遍历结果}
};
以下题为例：
traversal(1):
- 添加 1
- 调用 traversal(2)
traversal(2):
- 添加 2
- 调用 traversal(4)
traversal(4):
- 添加 4
- traversal(4->left) 返回（空）
- traversal(4->right) 返回（空）
回到 traversal(2):
- 调用 traversal(5)
traversal(5):
- 添加 5
- traversal(5->left) 返回
- traversal(5->right) 返回
回到 traversal(2) 结束
回到 traversal(1):
- 调用 traversal(3)
traversal(3):
- 添加 3
- traversal(3->left) 返回
- traversal(3->right) 返回
遍历完成
学会了前序遍历，那么中序遍历和后续遍历都是一个道理~
2.二叉树的中序遍历
给定一个二叉树的根节点root，返回它的中序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
class Solution {
public:// 递归遍历函数void traversal(TreeNode* cur, vector<int>& res) {// 1. 递归终止条件：当前节点为空if (cur == nullptr) return;// 2. 递归遍历左子树traversal(cur->left, res);// 3. 递归遍历右子树traversal(cur->right, res);// 4. 访问根节点（后序遍历的核心操作）res.push_back(cur->val); // 将当前节点值加入结果数组}// 主函数：二叉树的后序遍历vector<int> postorderTraversal(TreeNode* root) {vector<int> result; // 创建结果数组traversal(root, result); // 调用递归函数return result; // 返回遍历结果}
};
3.二叉树的后续遍历
给你一棵二叉树的根节点root，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
解释：
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
解释：
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
class Solution {
public:// 递归遍历函数void traversal(TreeNode* cur, vector<int>& res) {// 1. 递归终止条件：当前节点为空if (cur == nullptr) return;// 2. 递归遍历左子树traversal(cur->left, res);// 3. 递归遍历右子树traversal(cur->right, res);// 4. 访问根节点（后序遍历的核心操作）res.push_back(cur->val); // 将当前节点值加入结果数组}// 主函数：二叉树的后序遍历vector<int> postorderTraversal(TreeNode* root) {vector<int> result; // 创建结果数组traversal(root, result); // 调用递归函数return result; // 返回遍历结果}
};
4.二叉树的层序遍历
给你二叉树的根节点root，返回其节点值的 层序遍历。（即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
- 解题思路：
1.初始化队列：将根节点加入队列。
2.层级遍历：
- 记录当前层节点数。
- 依次处理当前层所有节点。
- 将子节点加入队列。
3.存储层级结果：将当前层节点值存入结果。
4.重复：继续处理下一层。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que; //创建队列用于BFS//如果根节点非空，将其加入队列if (root != nullptr) que.push(root);//创建结果容器，每层一个子数组vector<vector<int>> result;//当队列非空时，继续处理while (!que.empty()) {//1. 获取当前层节点数量int size = que.size();//创建当前层的值容器vector<int> res;//2. 遍历当前层所有节点for (int i = 0; i < size; i++) {//获取队首节点并出队TreeNode* node = que.front();que.pop();//存储当前节点值vec.push_back(node->val);//3. 将子节点加入队列（下一层）if (node->left) que.push(node->left);if (node->right) que.push(node->right);}//4. 将当前层结果加入总结果result.push_back(res);}return result; // 返回按层组织的节点值}
};
以下题为例：
| 步骤 | 队列状态 | 当前层节点 | 操作 | 当前层结果 | 总结果 |
|---|---|---|---|---|---|
| 1 | [3] | 1 | 初始化队列，根节点3入队 | [] | |
| 1 | [3] | 1 | 处理节点3：弹出3，值加入当前层 | [3] | |
| 1 | 将3的左子9入队 | ||||
| 1 | 将3的左子20入队 | ||||
| 1 | [9， 20] | 当前层完成，加入总结果 | |||
| 2 | [9， 20] | 2 | 处理第一个节点9：弹出9，值加入当前层 | [9] | |
| 2 | [20] | 9无子节点 | |||
| 2 | [20] | 处理第二个节点20：弹出20，值加入当前层 | [9,20] | ||
| 2 | 将20的左子15入队 | ||||
| 2 | 将20的左子7入队 | ||||
| 2 | [15,7] | 当前层完成，加入总结果 | [[3], [9,20]] | ||
| 3 | [15,7] | 2 | 处理第一个节点15：弹出15，值加入当前层 | [15] | [[3], [9,20]] |
| 3 | [7] | 15无子节点 | |||
| 3 | [7] | 处理第二个节点7：弹出7，值加入当前层 | [15,7] | [[3], [9,20]] | |
| 3 | [] | 7无子节点 | |||
| 3 | 当前层完成，加入总结果 | [[3], [9,20], [15,7]] | |||
| 4 | [] | 0 | 队列为空，遍历结束 | [[3], [9,20], [15,7]] |