二叉树的层序遍历

力扣二叉树专题（一）介绍了二叉树的深度优先遍历，前中后序的递归、迭代、统一迭代实现。二叉树还有一种遍历方式就是广度优先遍历，而层序遍历就是应用在二叉树上的广度优先遍历。

层序遍历一个二叉树，就是从左到右一层一层的去遍历二叉树。

栈先进后出适合模拟深度优先遍历，即递归逻辑；队列先进先出，符合一层一层遍历的逻辑，即层序遍历的逻辑。

再次回顾，对于二叉树的遍历总共8种：

• 前序遍历
• 中序遍历
• 后续遍历
• 深度优先搜索（DFS）
• 宽度优先搜索（BFS）
• Morris（莫里斯）的前中后3种遍历方式

前中后序遍历看力扣二叉树专题（一），以下是DFS和BFS对层序遍历的C++实现

★★★1. 二叉树的层序遍历-题102-遍历法和迭代法

这道题提供了层序遍历的模板！后面的九个题都可以套用！

迭代法思路： 先处理根节点，即存入大vector容器result中；再使用队列从左到右访问单层节点，并把当前层的所有节点值存在小vector容器v中。

迭代法做法：

1. 使用队列que遍历节点
2. 先处理根节点，往队列que存入根节点
3. 再从上之下，处理单层节点
4. 单层处理时，从左至右依次遍历节点，遍历次数就是队列que当前的大小，并准备一个小容器存放当前层所有节点值
5. 遍历当前层时，访问队列头部节点，弹出，存入小容器。然后队列需要按照从左至右的顺序更新为下一层的节点。
6. 当前层遍历结束后，小容器存入大容器，即当前层所有节点值存入

class Solution {
public://1.迭代法vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;//1.使用队列遍历节点queue<TreeNode*> que;//2.先处理根节点 队列存入根节点if(root!=nullptr) que.push(root);//3.再处理下一层节点while(!que.empty()){//4.每一层处理 每一层从左至右依次遍历节点 遍历次数就是队列的大小int size = que.size();vector<int> v;//存放每一层的节点值for(int i=0; i<size ;i++){TreeNode* cur = que.front();//访问队列头部节点que.pop();v.push_back(cur->val);//存入当前层的所有节点值//5.当前层节点处理完，队列元素需要更新为下一层的节点 左到右的顺序if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}//6.当前层的所有节点值存入大容器中result.push_back(v);}return result;}
};

递归法思路： 单层所有节点依次存入容器中，注意递归法的三个确定。

递归三个确定

1. 确定参数和返回值 参数应该是要传入指针 存放结果的容器 当前层的节点个数；不需要返回值 存入结果即可
2. 确定结束条件：所有的节点都遍历完了，指针为空则结束
3. 确定单次递归操作：当前层的节点依次存入容器

递归法做法：

1. 初始状态应该是传入根节点、存放结果的容器以及默认为0的深度
2. 首先判断节点是否为空，为空则说明遍历结束，直接返回；
3. 然后，剔除空树的情况
4. 接着，才是单层处理，当前层的所有节点存入容器即可
5. 最后，递归，按照从左到右的顺序，依次处理下一层的左节点、右节点

class Solution {
public://2.递归void order(TreeNode* cur, vector<vector<int>>& result, int depth){//1.递归结束 空指针不入队列if(cur==nullptr) return;//2.空树情况if(result.size()==depth) result.push_back(vector<int>());//3.当前层节点存入容器result[depth].push_back(cur->val);//下一层节点 深度要+1 假设每个节点都有两个孩子 当前节点有两个子节点order(cur->left, result, depth+1);//左order(cur->right, result, depth+1);//右}vector<vector<int>> levelOrder(TreeNode* root){vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

2. 二叉树的层次遍历II-题107

在题102的基础上，反转数组即可。

递归法

class Solution {
public:void order(TreeNode* cur, vector<vector<int>>& result, int depth){//递归结束条件if(cur==nullptr) return;//空树if(result.size()==depth) result.push_back(vector<int>());//单层存入result[depth].push_back(cur->val);//递归 下一层 从左至右order(cur->left, result, depth+1);order(cur->right, result, depth+1);}vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> result;int depth=0;order(root, result, depth);reverse(result.begin(), result.end());return result;}
};

迭代法

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> result;queue<TreeNode*> que;//1.根节点if(root!=nullptr) que.push(root);//下一层节点while(!que.empty()){int size = que.size();//遍历次数vector<int> v;//存放每一层所有节点值for(int i=0; i<size; i++){TreeNode* cur=que.front();que.pop();v.push_back(cur->val);//存放当前层节点if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}result.push_back(v);//存放当前层所有节点}reverse(result.begin(), result.end());return result;}
};

3. 二叉树的右视图-题199

迭代法： 每次存节点时，保证存放的是当前层最后一个节点即可

class Solution {
public://1.迭代法vector<int> rightSideView(TreeNode* root) {vector<int> result;queue<TreeNode*> que;//先处理根节点if(root!=nullptr) que.push(root);while(!que.empty()){int size = que.size();for(int i=0;i<size;i++){TreeNode* cur=que.front();que.pop();//注意！不能只存放右节点！而是存放右视图看到的节点！if(i==size-1) result.push_back(cur->val);//存放右节点 也就是每一层最后一个节点if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return result;}
};

递归法——搬运sweetiee的思路：

按照 「根结点 -> 右子树 -> 左子树」 的顺序访问，就可以保证每层都是最先访问最右边的节点，获取右视图的节点。

那么左视图就可以按照先序遍历的顺序 「根结点 -> 左子树 -> 右子树」 得到，先序遍历每层最先访问的是最左边的节点。

开始的时候，写的是根节点-左节点-右节点，输出一直是左视图。看到甜姨的思路才恍然大悟！

要注意，不能只存放右节点值，而是存放右视图看到的节点。如果只存放右节点，对于根节点只有一个左孩子的类似情况，无法正确存入。

class Solution {
public://递归法void order(TreeNode* cur, vector<int>& result, int depth){//1.递归结束条件 指针为空if(cur==nullptr) return;//3.只存放右视图看到的节点if(depth==result.size()) result.push_back(cur->val);depth++;order(cur->right, result, depth);order(cur->left, result, depth);}vector<int> rightSideView(TreeNode* root) {vector<int> result;int depth=0;order(root, result, depth);return result;}
};

4. 二叉树的层平均值-题637

思路： 在题107的基础上多了一个求和求均值的步骤，其他一样

迭代法：

class Solution {
public://迭代法vector<double> averageOfLevels(TreeNode* root) {vector<double> result;queue<TreeNode*> que;//先处理根节点if(root!=nullptr) que.push(root);while(!que.empty()){double size = que.size();double sum = 0;for(int i=0;i<size;i++){TreeNode* cur = que.front();que.pop();sum += cur->val;//所有节点值求和if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}result.push_back(sum/size);//存入当前层的平均值}return result;}
};

递归法

• 想用map key表示节点数，value表示和，但是节点数不一定是1、2、3…，有可能每一层只有一个节点
• 用一个vector，这个直接存放均值，但是不知道怎么维护节点值的和
• 可以用vector和pair来创建对组，first存放单层节点数，second存放单层节点和，但最后还是要另外每一组求均值存在另一个vector中
• 直接用两个vector，一个维护节点和，一个维护节点数

class Solution {
public://递归法void order(TreeNode* cur, vector<double>& sum, vector<int>& num, int depth)//3.确定递归传入的参数和返回值{//1.确定递归结束条件if(cur==nullptr) return;//2.确定递归单次操作 求和 保存单层节点数//多节点if(depth<sum.size()){sum[depth] += cur->val;num[depth] += 1;}//单节点else{sum.push_back(1.0* cur->val);num.push_back(1);}if(cur->left) order(cur->left, sum, num, depth+1);if(cur->right) order(cur->right, sum, num, depth+1);}vector<double> averageOfLevels(TreeNode* root) {//求和 节点数vector<double> sum;vector<int> num;int depth=0;order(root, sum, num, depth);//求均值vector<double> result;int size = sum.size();for(int i=0;i<size;i++){result.push_back(sum[i]/num[i]);}return result;}
};

★★★5. N叉树的层序遍历-题429-遍历法和迭代法

N叉树模板！

迭代法： 重点在于孩子节点依次存入队列中

class Solution {
public://迭代法vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> result;queue<Node*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size=que.size();vector<int> v;for(int i=0;i<size;i++){Node* cur=que.front();que.pop();v.push_back(cur->val);//不同点 孩子节点放进队列中for(int j=0;j<cur->children.size();j++){if(cur->children[j]) que.push(cur->children[j]);}}result.push_back(v);}return result;}
};

递归法： 重点在于递归时孩子节点的更新

class Solution {
public://递归法void order(Node* cur, vector<vector<int>>& result, int depth){if(cur==NULL) return;//递归结束条件if(depth==result.size()) result.push_back(vector<int>());//空树result[depth].push_back(cur->val);//更新节点for(int i=0;i<cur->children.size();i++){order(cur->children[i], result, depth+1);}}vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> result;int depth=0;order(root, result, depth);return result;}
};

6. 在每个树行中找最大值-题515

迭代法思路： 层序遍历，取每一层的最大值。关键在于，先假设一个最大值，最大值与节点值比较

class Solution {
public://迭代法vector<int> largestValues(TreeNode* root) {vector<int> result;queue<TreeNode*> que;if(root!=nullptr) que.push(root);while(!que.empty()){int size = que.size();int max = INT_MIN;for(int i=0;i<size;i++){TreeNode* cur = que.front();que.pop();//找最大值max = max > cur->val? max : cur->val;if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}result.push_back(max);}return result;}
};

递归法思路： 递归法还是传入存放结果的容器、节点指针、树的深度。在找最大值时，通过深度控制，不停地比较容器存放的值与当前节点值。深度与容器大小相等时，说明该层节点都比较完了。

class Solution {
public://递归void order(TreeNode* cur, vector<int>& result, int depth){if(cur==nullptr) return;//单次操作 找最大值 更新节点//找最大值时，不停比较 单层节点都比较if(depth==result.size()) result.push_back(cur->val);else result[depth] = max(result[depth], cur->val);order(cur->left, result, depth+1);order(cur->right, result, depth+1);}vector<int> largestValues(TreeNode* root){vector<int> result;int depth = 0;order(root, result, depth);return result;}
};

7. 填充每个节点的下一个右侧节点指针-题116-满二叉树

迭代法

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;if(root!=NULL) que.push(root);while(!que.empty()){int size=que.size();Node* cur;Node* pre;for(int i=0;i<size;i++){//根节点if(i==0){pre = que.front();que.pop();cur=pre;//记录当前层头节点}else{cur = que.front();que.pop();pre->next=cur;//上一层父节点连向其左子节点；左子节点连向右子节点  本层前一个节点next指向本节点pre=pre->next;//pre更新为左子节点；pre更新为当前层的下一个节点    节点偏移}if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}pre->next=NULL;//当前层最后一个节点指向空 }return root;}
};

递归法

class Solution {
public://递归法void link(Node* root){if(root==NULL || root->left==NULL) return;//说明遍历结束root->left->next = root->right;//左节点指向右节点if(root->next) root->right->next = root->next->left;link(root->left);link(root->right);}Node* connect(Node* root){link(root);return root;}
};

if(root->next) root->right->next = root->next->left;的解释：

这是个满二叉树，前面已经判断过root->left !=null 才能走到这个逻辑。

所以，root的下一层必然是满的，因此if(root->next)，也就是说root->next !=null表明了，root必不是该层的最右节点。

所以root->right、root->right-next、root->next->left都不可能为null，只有root到该层最右节点时，root->right、root->right-next、root->next->left为null，最右节点指向null

8. 填充每个节点的下一个右侧节点指针II-题117-二叉树

和上一题类似，只是这个是二叉树，不是满二叉树。

迭代法： 可以直接套用上一题的代码

class Solution {
public:Node* connect(Node* root) {queue<Node*> que;//1.空指针不入队列if(root!=NULL) que.push(root);//2.开始遍历所有节点while(!que.empty()){//3.两个指针 遍历当前层的节点数 一个指针记录当前层头节点 一个用来连接Node* pre;Node* cur;int size = que.size();//4.遍历当前层节点for(int i=0; i<size; i++){//5.处理头节点 if(i==0){pre = que.front();que.pop();cur = pre;//记录头节点}else{cur = que.front();//访问要处理的节点que.pop();pre->next = cur;//本层上一个节点 连向 本层的节点pre = pre->next;//pre偏移 更新  让当前节点成为前一个节点}//6.更新队列if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}//最右节点指向空pre->next = NULL;}return root;}
};

递归法：
首先判断当前节点的状态：1.节点为空 2.节点有左右子节点 3.节点只有左子节点 4.节点有右子节点。根据节点的不同状态作不同的处理，最后对函数做递归调用实现对节点左右子树的遍历。具体过程看注释

注意： 一定要先遍历右子树，完成对右子树节点next域的构建，然后再对左子树遍历，才能实现对左子树中孤立左子节点和右子节点next域的构建

class Solution {
public://递归法//1.找到有效节点Node* findNode(Node* node){if(node==NULL) return NULL;//4.空节点 返回nullelse{//节点非空while(node){if(node->left) return node->left;//2.只有左子节点if(node->right) return node->right;//3.右只有右子节点node = node->next;//1.节点有左右子节点}return node;}}//2.递归Node* connect(Node* root){//1.如果节点为空，返回null 遍历结束if(root==NULL)  return root;//如果节点的左右子节点都不为空，三种情况判断//3.只有右节点非空，遍历当前节点的next域，寻找符合条件的next指向if(root->right) root->right->next = findNode(root->next);//4.只有左节点非空 还需要判断右节点是否为空//右节点不为空 左节点指向右节点；//右节点为空，就要遍历当前节点的next域，寻找符合条件的next指向 左节点指向符合条件的next指向if(root->left) root->left->next = root->right ? root->right : findNode(root->next);//5.递归  先更新右子树节点，再是左子树 不能反//因为要先把右子树的next域构建好，左子树才能在节点的next域找到正确的next指向。//如果反着来，会先构建左子树，导致当前节点的next域还未构建好，遗漏掉一些节点的next域，使结果出错connect(root->right);connect(root->left);return root;}
};

★★★9. 二叉树的最大深度-题104

找深度模板！

1. 迭代法，两个数组存节点，最后返回大数组的大小，超笨的方法

class Solution {
public://1.迭代法int maxDepth(TreeNode* root) {queue<TreeNode*> que;vector<vector<int>> V;if(root!=nullptr) que.push(root);while(!que.empty()){int size = que.size();vector<int> v;for(int i=0;i<size;i++){TreeNode* cur = que.front();que.pop();v.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}V.push_back(v);}return (int)V.size();}
};

2. 迭代法，一个数组存节点，当前层遍历完，计数，时间提升了

class Solution {
public://2.迭代法int maxDepth(TreeNode* root) {queue<TreeNode*> que;int count = 0;if(root!=nullptr) que.push(root);while(!que.empty()){int size = que.size();vector<int> v;for(int i=0;i<size;i++){TreeNode* cur = que.front();que.pop();v.push_back(cur->val);if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}count++;}return count;}
};

3. 迭代法，不用数组存节点，当前层遍历完，计数，时间介于1、2之间，内存比1、2好一点点，汗

class Solution {
public://3.迭代法int maxDepth(TreeNode* root){queue<TreeNode*> que;int depth=0;if(root) que.push(root);while(!que.empty()){int size = que.size();//遍历当前层所有节点for(int i=0;i<size;i++){TreeNode* cur = que.front();que.pop();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}depth++;}return depth;}
};

4. 递归法
   找出终止条件：当前节点为空
   找出返回值：节点为空时，说明高度为0，返回0；节点不为空时，则分别求左右子树的高度的最大值max，同时加1（ 表示当前节点的高度），返回max+1

class Solution {
public://4.递归法int maxDepth(TreeNode* root){if(root==nullptr) return 0;int l = maxDepth(root->left);int r = maxDepth(root->right);return max(l,r)+1;}
};

10. 二叉树的最小深度-题111

和上面那题很像，先说递归法，分四种情况

1. 空节点，返回0；
2. 父节点有两个左右子节点，返回1+左右子树的最小值，1表示上一层；
3. 只有左子节点，返回1+左子树；
4. 只有右节点，返回1+右子树

class Solution {
public://递归法int minDepth(TreeNode* root) {if(root==nullptr) return 0;int num=1;int l=0, r=0;if(root->left!=nullptr && root->right!=nullptr){l = minDepth(root->left);r = minDepth(root->right);num +=  min(l, r);}else if(root->left!=nullptr && root->right==nullptr){num += minDepth(root->left);}else num += minDepth(root->right);return num;}
};

迭代法：要注意只有左右孩子都为空的时候，才说明遍历的最低点了。如果其中一个孩子为空则不是最低点

class Solution {
public://迭代法int minDepth(TreeNode* root){queue<TreeNode*> que;if(root==nullptr) return 0; int depth = 0;que.push(root);while(!que.empty()){int size = que.size();depth++;for(int i=0;i<size;i++){TreeNode* cur=que.front();que.pop();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);if(cur->left==nullptr && cur->right==nullptr) return depth;//遍历到最低点}}return depth;}
};

太好了，这10个题结束了！