03层次遍历
# 02 层次遍历
通常使用广度优先搜索进行层次遍历。注意，不需要使用两个队列来分别存储当前层的节点和下一层的节点，因为在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数，只要控制遍历这么多节点数，就能保证这次遍历的都是当前层的节点。
# 102 二叉树的层序遍历 (opens new window)
实现二叉树的层序遍历
输入一个二叉树，输出一个二维数组，表示二叉树层序遍历的结果
输入：[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7输出：
[ [3], [9,20], [15,7] ]
解析：
通常使用广度优先搜索进行层次遍历，使用一个队列存储当前层的所有节点。
在开始遍历一层的节点时，当前队列中的节点数就是当前层的节点数。
只要控制遍历这么多节点数，每遍历一个当前层的节点，将其出队列同时将其子节点入队列。
通过这种操作就能保证每次遍历的队列中都是当前层的节点。
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==nullptr){
return res;
}
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int queLen = que.size();
vector<int> levelElem;
for(int i=0;i<queLen;++i){
auto node = que.front();
que.pop();
levelElem.push_back(node->val);
if(node->left){
que.push(node->left);
}
if(node->right){
que.push(node->right);
}
}
res.push_back(levelElem);
}
return res;
}
};
# 637 二叉树的层平均值 (opens new window)
给定一个二叉树，求每一层的节点值的平均数。
输入是一个二叉树，输出是一个一维数组，表示每层节点值的平均数。
输入：
3 / \ 9 20 / \ 15 7输出：[3, 14.5, 11] 解释：第 0 层的平均值是 3 , 第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。
解析：
使用一个先入先出的队列对二叉树进行层次遍历，遍历每一层的过程中累计该层的总和并在最后将平均值加入结果集。
使用双层循环完成每层均值计算：外循环逐层遍历二叉树；内循环遍历队列中当前层的所有节点，计算当前层节点值均值，并将下一层节点压入队列。
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
if(!root){
return ans;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int len = q.size();
double sum = 0;
for(int i=0;i<len;++i){
auto node = q.front();
q.pop();
sum+=node->val;
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
ans.push_back(sum/len);
}
return ans;
}
};
# 513 找树左下角的值 (opens new window)
给定一个二叉树，找出该二叉树的 最底层 最左边 节点的值
输入一个二叉树，输出一个整型值表示该二叉树左下角的值
输入: root = [2,1,3] 输出: 1
解析：
本题很容易想到使用层次遍历解决，因为二叉树的 最底层 最左边 节点的值就是层次遍历最后一层的第一个节点值。
所以，本题仅需要得到二叉树的层次遍历结果，然后将最后一层的第一个值返回即可。
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int ans = 0;
if(!root){
return ans;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int queLen = q.size(); // 要记录最初的队列长度，不然在后续push和pop操作中会影响该值
ans = q.front()->val; // 记录当前层的第一个值
for(int i=0;i<queLen;++i){
auto node = q.front();
q.pop();
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}
return ans;
}
};
# 662 二叉树最大宽度 (opens new window)
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
示例:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
解析：
- 宽度优先会使用一个queue，而这个queue就可以帮助我们计算出目前层的宽度
- 数值转换(关键一步，减少内存，加速计算)：为了计算宽度，我们需要记录每个节点出现的编号， 比如[1,3,2] 这样的二叉树，对应 1->0 3->0 2->1
- 下一层，基于当前层的编号推出下一层：
- left: parent->val * 2
- right: parent->val * 2 +1
- 当前层的宽度： back-val - front->val + 1
- 如 front->0 back=4, 那么宽度就是5
- 额外，为了避免数字过大，我们会让val每次基于queue front编号做缩小
- queue front的编号是100
- front缩小为 100-100=0， 后续每个编号都需要减去100
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root){
return 0;
}
queue<pair<TreeNode*,long long>> q; //pair的第二个位置记录当前是第几个节点
q.push(make_pair(root,1));
int ans = 0;
while(!q.empty()){
//start是本层起点, index是本层当前遍历到的节点的索引
int len = q.size();
long long start = q.front().second;
long long index;
for(int i=0;i<len;++i){
auto node = q.front().first;
index = q.front().second;
q.pop();
if(node->left){
// -start*2 防止索引位置太大溢出
q.push(make_pair(node->left,index*2-start*2));
}
if(node->right){
q.push(make_pair(node->right,index*2+1-start*2));
}
}
int wid = index-start+1;
ans = max(ans,wid);
}
return ans;
}
};