代码随想录算法训练营第十三天|二叉树的递归遍历、 二叉树的迭代遍历、二叉树的层次遍历

day13

1. 二叉树的递归遍历

递归算法的三个要素。每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

• 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

• 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

• 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以下以前序遍历为例：

• 确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

void traversal(TreeNode* cur, vector<int>& vec)

• 确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if (cur == NULL) return;

• 确定单层递归的逻辑：前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

前序遍历：

class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val);    // 中traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

那么前序遍历写出来之后，中序和后序遍历就不难理解了，代码如下：

中序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左vec.push_back(cur->val);    // 中traversal(cur->right, vec); // 右
}

后序遍历：

void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec);  // 左traversal(cur->right, vec); // 右vec.push_back(cur->val);    // 中
}

此时做一做leetcode上三道题目，分别是：

(1) 144二叉树的前序遍历

(2) 145二叉树的后序遍历

(3) 94二叉树的中序遍历

2. 二叉树的迭代遍历

**前序遍历（迭代法）**思路如下：

(1) 初始化：

• 如果 root 为 NULL，返回空的结果数组。
• 创建栈 st，将根节点 root 压入栈中。
• 创建结果数组 result。

(2) 循环遍历：

• 当栈不为空时，取出栈顶节点 node 并弹出，加入 result。
• 先将 node 的右子节点（如果有）压入栈，再将左子节点（如果有）压入栈。

(3) 返回结果：

• 当栈为空时，遍历结束，result 中即为先序遍历结果。

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();                       // 中st.pop();result.push_back(node->val);if (node->right) st.push(node->right);           // 右（空节点不入栈）if (node->left) st.push(node->left);             // 左（空节点不入栈）}return result;}
};

**中序遍历（迭代法）**思路如下：

(1) 初始化：

• 创建 result 数组用于保存遍历结果。
• 创建栈 st 和指针 cur 指向根节点 root。

(2) 遍历左子树到最底层：

• 当 cur 不为空时，将 cur 当前节点入栈并移动 cur 到左子节点，继续下探直到最左下的节点。

(3) 处理节点并访问右子树：

• 如果 cur 为 NULL 且栈非空：
  • 从栈顶弹出节点作为当前节点，将其值加入 result。
  • 将 cur 移动到该节点的右子节点，重复步骤 (2) 和 (3)。

(4) 返回结果：

• 当栈为空且 cur 为 NULL 时，遍历结束，result 中即为中序遍历结果。

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点，访问到最底层st.push(cur); // 将访问的节点放进栈cur = cur->left;                // 左} else {cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）st.pop();result.push_back(cur->val);     // 中cur = cur->right;               // 右}}return result;}
};

**后续遍历（迭代法）**思路如下：

前序遍历是中左右，后序遍历是左右中，那么我们只需要调整一下前序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();result.push_back(node->val);if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）if (node->right) st.push(node->right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};

3. 二叉树的层次遍历

思路：

(1) 初始化队列和结果列表：

• 创建一个队列 que 用于存储每层的节点，按照层序依次访问。
• 若根节点 root 不为空，将其入队。
• 创建 result 列表用于存储每层节点的值。

(2) 层序遍历循环：

• 进入主循环，只要队列 que 不为空，就表示还有未遍历的层。

(3) 处理每层的节点：

• 记录当前层的节点数量 size（此时队列中所有节点都是当前层的）。
• 创建一个 vec 列表用于存储当前层的节点值。

(4) 遍历当前层节点：

• 逐个访问当前层的 size 个节点：
  • 从队列头部弹出节点 node，将该节点的值加入 vec。
  • 如果 node 有左子节点，则将其入队；如果有右子节点，也将其入队。
• 这一层结束后，将 vec 添加到 result 中。

(5) 结束遍历并返回结果：

• 当队列为空时，所有层已遍历完成，返回 result 即为层序遍历结果。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;}
};

学会二叉树的层序遍历，可以一口气写完以下十题：

• 102.二叉树的层序遍历（代码同上）

• 107.二叉树的层次遍历II

基于层次遍历框架代码，只需将 result.push_back(vec); 替换为 result.insert(result.begin(), vec); 即可。

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.insert(result.begin(), vec); // 将每层的结果插入到 result 的开头}return result;}
};

• 199.二叉树的右视图

基于层次遍历框架代码，for循环中只需在 i==size-1 时（即最右的数）存入数组。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> vec;while (!que.empty()) {int size = que.size();// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if(i==size-1) vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return vec;}
};

• 637.二叉树的层平均值

因为题中结果带有小数点，所以基于层次遍历框架代码，首先需要将数组和数据的类型定义为double，其次定义double sum记录每一层节点的和，在for循环结束后将sum/size求一层节点的平均值。

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<double> vec;while (!que.empty()) {int size = que.size();double sum=0;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();sum+=node->val;//求一层节点的和if (node->left) que.push(node->left);if (node->right) que.push(node->right);}double average = sum/size;//求一层节点的平均值vec.push_back(average);}return vec;}
};

• 429. N叉树的层序遍历

基于层次遍历框架代码，只不过一个节点有多个孩子了，用个for循环将所有节点孩子加入队列

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {Node* node = que.front();que.pop();vec.push_back(node->val);for (int i = 0; i < node->children.size(); i++) { // 将节点孩子加入队列que.push(node->children[i]);}}result.push_back(vec);}return result;}
};

• 515.在每个树行中找最大值

基于层次遍历框架代码，for循环中只需找到每层最大的数存入数组

class Solution {
public:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> vec;while (!que.empty()) {int size = que.size();int max=INT_MIN;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();max=max<node->val?node->val:max;if (node->left) que.push(node->left);if (node->right) que.push(node->right);}vec.push_back(max);}return vec;}
};

• 116.填充每个节点的下一个右侧节点指针

基于层次遍历框架代码，在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();// vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

• 117.填充每个节点的下一个右侧节点指针II

这道题目说是二叉树，但116题目说是完整二叉树，其实没有任何差别，一样的代码一样的逻辑

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if (root != NULL) que.push(root);while (!que.empty()) {int size = que.size();// vector<int> vec;Node* nodePre;Node* node;for (int i = 0; i < size; i++) {if (i == 0) {nodePre = que.front(); // 取出一层的头结点que.pop();node = nodePre;} else {node = que.front();que.pop();nodePre->next = node; // 本层前一个节点next指向本节点nodePre = nodePre->next;}if (node->left) que.push(node->left);if (node->right) que.push(node->right);}nodePre->next = NULL; // 本层最后一个节点指向NULL}return root;}
};

• 104.二叉树的最大深度

基于层次遍历框架代码，只需在for循环结束后将result+1即可，一个for循环代表一层

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result=0;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result+=1;}return result;}
};

• 111.二叉树的最小深度

基于层次遍历框架代码，当左右孩子都为空的时候，说明到遍历的最低点了，return depth

class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);int result=0;while (!que.empty()) {int size = que.size();vector<int> vec;result+=1;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);if (!node->left&&!node->right) return result;}}return result;}
};