本文最后更新于 273 天前，其中的信息可能已经有所发展或是发生改变。
二叉树的层序遍历往往用在求树宽，求树深的一类题中会频繁用到。
思想：使用一个队列，出队的同时将节点的左右孩子都入队即可
- 注意遍历时先取出一层的size，否则随着左右孩子入队，其size会动态变化
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* <em>root</em>) {
<em>if</em> (!root)
<em>return</em> {};
vector<vector<int>> res;
int size;
queue<TreeNode*> que;
que.push(root);
<em>while</em> (!que.empty()) {
vector<int> cur_res;
size = que.size();
<em>for</em> (int i = 0; i < size; i++) {
TreeNode* cur = que.front();
que.pop();
cur_res.push_back(cur->val);
<em>if</em> (cur->left) que.push(cur->left);
<em>if</em> (cur->right) que.push(cur->right);
}
res.push_back(cur_res);
}
<em>return</em> res;
}
};相关题目：
- 102. 二叉树的层序遍历 – 力扣（LeetCode）
- 模板母体
- 107. 二叉树的层序遍历 II – 力扣（LeetCode）
- 描述：给你二叉树的根节点
root，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） - 思路：层序遍历 + reverse
- std::reverse(res.begin(), res.end());
- 描述：给你二叉树的根节点
- 104. 二叉树的最大深度 – 力扣（LeetCode）
- 实际上为res节点的个数
- 111. 二叉树的最小深度 – 力扣（LeetCode）
- 这个场景下我们不需要用到res，转而用depth记录深度。每记录一层depth+1,若无孩子则返回。
- 199. 二叉树的右视图 – 力扣（LeetCode）
- 右视图实际上就是层序便利的最后一个元素，实际上我们只需要记录循环中每一层的last one即可
- 637. 二叉树的层平均值 – 力扣（LeetCode）
- 多计算一次平均值即可
- 429. N 叉树的层序遍历 – 力扣（LeetCode）
- 在遍历孩子的时候改为
- for(auto child: node->children) { if (child) { que.push(child); } }
- 在遍历孩子的时候改为
- 515. 在每个树行中找最大值 – 力扣（LeetCode）
- 记录每一层的最大值
- 116. 填充每个节点的下一个右侧节点指针 – 力扣（LeetCode）
- 已知当前层，将当前层的节点串一遍即可
- 或者在层序便利的过程中记录上一个节点，直接串在一起
- 117. 填充每个节点的下一个右侧节点指针 II – 力扣（LeetCode）
- 这道题是二叉树，116给的完美二叉树，其实没有区别
层序遍历类题目完结。
