C++力扣题目-- 二叉树层序遍历

102.二叉树的层序遍历(opens new window)
107.二叉树的层次遍历II(opens new window)
199.二叉树的右视图(opens new window)
637.二叉树的层平均值(opens new window)
429.N叉树的层序遍历(opens new window)
515.在每个树行中找最大值(opens new window)
116.填充每个节点的下一个右侧节点指针(opens new window)
117.填充每个节点的下一个右侧节点指针II(opens new window)
104.二叉树的最大深度(opens new window)
111.二叉树的最小深度

102思路：

我们之前讲过了三篇关于二叉树的深度优先遍历的文章：

二叉树：前中后序递归法(opens new window)
二叉树：前中后序迭代法(opens new window)
二叉树：前中后序迭代方式统一写法(opens new window)

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：

102二叉树的层序遍历

这样就实现了层序从左到右遍历二叉树。

代码如下：这份代码也可以作为二叉树层序遍历的模板，打十个就靠它了。

c++代码如下：

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;}
};

107--将102的结果reverse即可；

C++代码：

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;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);}reverse(result.begin(), result.end()); // 在这里反转一下数组即可return result;}
};

199--二叉树的右视图

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

C++代码：

class Solution {
public: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;}
};

637--二叉树的层平均值

本题就是层序遍历的时候把一层求个总和在取一个均值。

C++代码:

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*>que;vector<double>result;if (root != nullptr) { que.push(root); }while (!que.empty()){            int 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); }}sum /= size;result.push_back(sum);}return result;}
};

429. N 叉树的层序遍历

这道题依旧是模板题，只不过一个节点有多个孩子了

C++代码:

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {queue<Node*>que;vector<vector<int>>result;if (root != nullptr) { que.push(root); }while (!que.empty()){int size = que.size();vector<int>tmp;for (int i = 0; i < size; i++){Node* cur = que.front();tmp.push_back(cur->val);que.pop();int vsize = cur->children.size();for(int j=0;j<vsize;j++){if (cur->children[j]) {que.push(cur->children[j]);}}}result.push_back(tmp);}return result;}
};

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

层序遍历，取每一层的最大值

C++代码：

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

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

思路

本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了

C++代码：

class Solution {
public:Node* connect(Node* root) {queue<Node*>que;if (root != nullptr) { que.push(root); }while (!que.empty()){int size = que.size();Node* pre;Node* cur;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;pre = pre->next;}if (cur->left) { que.push(cur->left); }if (cur->right) { que.push(cur->right); }}pre->next = nullptr;}return root;}
};

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

思路

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

C++代码：

class Solution {
public:Node* connect(Node* root) {queue<Node*>que;if (root != nullptr) { que.push(root); }while (!que.empty()){int size = que.size();Node* pre;Node* cur;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;pre = pre->next;}if (cur->left) { que.push(cur->left); }if (cur->right) { que.push(cur->right); }}pre->next = nullptr;}return root;}
};

104.二叉树的最大深度

思路

使用迭代法的话，使用层序遍历是最为合适的，因为最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度，如图所示：

层序遍历

所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

C++代码如下:

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*>que;int depth = 0;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 (cur->left) { que.push(cur->left); }if (cur->right) { que.push(cur->right); }}depth++;}return depth;}
};

111.二叉树的最小深度

思路

相对于 104.二叉树的最大深度，本题还也可以使用层序遍历的方式来解决，思路是一样的。

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

代码如下：（详细注释）

class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*>que;int depth = 0;if (root != nullptr){que.push(root);}else {return depth;}                           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;}
};