二叉树层序遍历

在本文中，我将会选取LeetCode上二叉树层序遍历的多道例题，并给出解答，通过多道题我们就可以发现，二叉树的层序遍历并不复杂，并且有着共通点。

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思考：

本题又是一种新的二叉树遍历方式，层序遍历，这种遍历方式其实较为简单，符合正常的遍历顺序。所以我们可以采用队列这种数据结构，运用其先进先出的特性进行遍历。

利用队列遍历：

本题要求按每一层遍历，所以我们采用for循环的形式，进行每一层的遍历。值得注意的是，随着结点加入队列中，队列的大小也会随之改变，所以在进行for循环之前，需要提前存储队列的大小size。

/*** Definition for a binary tree node.* 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<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()){vector<int> childvector;//子容器，储存每一层遍历的结果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);}childvector.push_back(cur->val);}result.push_back(childvector);}return result;}
};

递归法：

当然，该题也可以使用递归法来实现，该题中，递归的终止条件为：遍历到空节点，此时说明已将所有结点遍历完毕，进行返回，结束递归。每轮递归中，利用depth记录层数，当进入新的一层时，创建新的子容器。

//递归法
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>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

思考：

本题与102. 二叉树的层序遍历类似，只需在102题的基础上，对最后的result数组进行翻转操作即可。

代码：

#include <iostream>
#include<vector>
#include<queue>using namespace std;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<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()){vector<int> childvector;//子容器，储存每一层遍历的结果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);}childvector.push_back(cur->val);}result.push_back(childvector);}return result;}
};

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

思考：

本题仍然是一道经典的层序遍历二叉树的题，题意要求只输出最右侧的结点，所以我们只需要在每层for循环中加以判断，只输出目标结点即可。

代码：

#include <iostream>
#include<vector>
#include<queue>using namespace std;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<int> rightSideView(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()){vector<int> childvector;//子容器，储存每一层遍历的结果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);}if (i == (size - 1)){result.push_back(cur->val);//只输出最后一个结点}}}return result;}
};

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

提示：

树中节点数量在 [1, 10⁴] 范围内
-2³¹ <= Node.val <= 2³¹ - 1

思考：

本题的本质其实还是二叉树的层序遍历，区别在于在遍历完成后，要求取每一层的平均值，并进行输出。

代码：

值得注意的是，这里需要返回的值时double类型的。

#include <iostream>
#include<vector>
#include<queue>using namespace std;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<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<double> result;while (!que.empty()){double sum = 0;//记录每一层的和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);}sum += cur->val;}result.push_back(sum/size);}return result;}
};

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000
树的节点总数在 [0, 10^4] 之间

思考：

本题又是一道层序遍历题，但这一次的树不再是二叉树，而是一棵N叉树，每个节点都有可能有多个儿子，而不是像二叉树只含有左右结点，这就要求我们呢在遍历时做出一些调整。

代码：

在进行子儿子遍历时，再采取一层for循环，能够完成完整的遍历。

#include <iostream>
#include<vector>
#include<queue>using namespace std;class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};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()){vector<int> childvector;//子容器，储存每一层遍历的结果int size = que.size();//记录队列当前大小for (int i = 0; i < size; i++){Node* cur = que.front();que.pop();for (int i = 0; i < cur->children.size(); i++){if(cur->children[i]){que.push(cur->children[i]);}}childvector.push_back(cur->val);}result.push_back(childvector);}return result;}
};

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

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

二叉树的节点个数的范围是 [0,104]
-2³¹ <= Node.val <= 2³¹ - 1

思考

本题所考察的仍然是二叉树的层序遍历，只需要在每一层遍历时找出最大值即可。

代码：

#include <iostream>
#include<vector>
#include<queue>using namespace std;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<int> largestValues(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<int> result;while (!que.empty()){int size = que.size();//记录队列当前大小int max= INT_MIN;//初始化每一层的最大值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);}max = cur->val > max ? cur->val:max;//更新最大值}result.push_back(max);}return result;}
};

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

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {int val;Node *left;Node *right;Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

提示：

树中节点的数量在 [0, 2¹² - 1] 范围内
-1000 <= node.val <= 1000

思考：

本题的题意比较难懂，其实就是在每一层的层次遍历时记录下本层的头结点，并且在遍历时让前一个结点指向该结点即可。

代码：

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题也完全可以使用以上代码，以上的求解过程与是否为完美二叉树并没有关系)

参考：代码随想录

往期回顾：
LeetCode102. 二叉树的层序遍历
LeetCode144、145、94. 二叉树遍历
LeetCode18. 四数之和
LeetCode15. 三数之和
LeetCode383. 赎金信
LeetCode454. 四数相加 II
LeetCode1. 两数之和
LeetCode202. 快乐数
LeetCode350. 两个数组的交集 II
LeetCode349. 两个数组的交集
LeetCode1002. 查找共用字符