【力扣总结】一口气刷完二叉树层次遍历的十道题（C++代码）

LeetCode二叉树打卡day5

代码随想录链接
溺记录一下二叉树层次遍历的经典面试题

1.二叉树的层序遍历

原题链接

1.1题意：

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

1.2思路：

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

使用队列来完成操作。
因为队列的特点是先进先出，所以每次都是左边节点的子节点先进入队列，然后右边节点的子节点再进入队列，这样就保证了对于子节点来说也是从左到右的遍历顺序。
注意每一次要先记录队列的大小，此时队列的大小就是这一层的节点个数。

1.3代码：

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        queueq;
        vector>ans;
        if(!root) return ans;
        q.push(root);
        while(!q.empty()){
            vectortmp;
            int cnt=q.size();
            while(cnt--){
                TreeNode* t=q.front();
                q.pop();
                tmp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

2.二叉树的层序遍历 II

原题链接

2.1题意：

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

2.2思路：

如果是要求自底向上的遍历的话，只需要最后将数组翻转。
添加代码reverse(ans.begin(),ans.end());

2.3代码：

class Solution {
public:
    vector> levelOrderBottom(TreeNode* root) {
        queueq;
        vector>ans;
        if(!root) return ans;
        q.push(root);
        while(!q.empty()){
            vectortmp;
            int cnt=q.size();
            while(cnt--){
                TreeNode* t=q.front();
                q.pop();
                tmp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ans.push_back(tmp);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

3. 二叉树的右视图

原题链接

3.1题意：

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

3.2思路：

答案相当于是每一层节点的最右边的节点，所以在遍历的时候当遇到最右边的节点时，就将该节点记录。
添加的代码if(i==cnt) ans.push_back(now->val);

3.3代码：

class Solution {
public:
    vector rightSideView(TreeNode* root) {
        vectorans;
        if(!root) return ans;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cnt=q.size();
            for(int i=1;i<=cnt;i++){
                TreeNode* now=q.front();
                q.pop();
                if(i==cnt) ans.push_back(now->val);
                if(now->left) q.push(now->left);
                if(now->right) q.push(now->right);
            }
        }
        return ans;
    }
};

4.二叉树的层平均值

原题链接

4.1题意：

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

4.2思路：

在遍历的时候统计每层的元素和，最后将元素和除以元素个数就是平均值。
添加代码sum+=1ll*t->val; ans.push_back(sum*1.0/cnt);

4.3代码：

class Solution {
public:
    vector averageOfLevels(TreeNode* root) {
        vectorans;
        if(!root) return ans;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cnt=q.size();
            long long sum=0;
            for(int i=1;i<=cnt;i++){
                TreeNode* t=q.front();q.pop();
                sum+=1ll*t->val;
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ans.push_back(sum*1.0/cnt);
        }
        return ans;
    }
};

5.N 叉树的层序遍历

原题链接

5.1题意：

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

5.2思路：

N叉树的遍历跟二叉树的本质是一样的，在取出该节点的时候，如果是二叉树就将左儿子和右儿子放入队列；如果N叉树就将所有的子节点放入队列。
for(Node* tt:t->children){ if(tt) q.push(tt); }

5.3代码：

class Solution {
public:
    vector> levelOrder(Node* root) {
        vector>ans;
        if(!root) return ans;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cnt=q.size();
            vectortmp;
            while(cnt--){
                Node* t=q.front();q.pop();
                tmp.push_back(t->val);
                for(Node* tt:t->children){
                    if(tt) q.push(tt);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

6.在每个树行中找最大值

原题链接

6.1题意：

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

6.2思路：

在遍历的时候维护每一层的最大值。
添加代码if(i==1) maxx=t->val; else maxx=max(maxx,t->val);

6.3代码：

class Solution {
public:
    vector largestValues(TreeNode* root) {
        vectorans;
        if(!root) return ans;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cnt=q.size(),maxx;
            for(int i=1;i<=cnt;i++){
                TreeNode* t=q.front();q.pop();
                if(i==1) maxx=t->val;
                else maxx=max(maxx,t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ans.push_back(maxx);
        }
        return ans;
    }
};

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

原题链接

7.1题意：

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

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

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

7.2思路：

设置上一个节点为las，每次都将las的next节点设置为当前节点；如果当前节点为最后一个节点，设置当前节点的next为NULL。
添加代码if(i!=1){ las->next=t;las=t; if(i==cnt) t->next=NULL; } else{ las=t; }

7.3代码：

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cnt=q.size();
            Node* las;
            for(int i=1;i<=cnt;i++){
                Node* t=q.front();q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                if(i!=1){
                    las->next=t;las=t;
                    if(i==cnt) t->next=NULL;
                }
                else{
                    las=t;
                }
            }
        }
        return root;
    }
};

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

原题链接

8.1题意：

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

8.2思路：

8.3代码：

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cnt=q.size();
            Node* las;
            for(int i=1;i<=cnt;i++){
                Node* t=q.front();q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                if(i!=1){
                    las->next=t;las=t;
                    if(i==cnt) t->next=NULL;
                }
                else{
                    las=t;
                }
            }
        }
        return root;
    }
};

9.二叉树的最大深度

原题链接

9.1题意：

给定一个二叉树，找出其最大深度。

9.2思路：

可以用递归来做，也可以用层次遍历来做。
层次遍历的做法是：设置答案dep为0，每次遍历一层都让dep++
最后dep就是答案

9.3代码：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        queueq;
        q.push(root);
        int dep=0;
        while(!q.empty()){
            int cnt=q.size();
            dep++;
            for(int i=1;i<=cnt;i++){
                TreeNode* t=q.front();q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return dep;
    }
};

10.二叉树的最小深度

原题链接

10.1题意：

给定一个二叉树，找出其最小深度。

10.2思路：

只有当左右孩子都为空的时候，才说明遍历的最低点了，这时候答案才是最小深度。如果其中一个孩子为空则不是最低点。

10.3代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        queueq;
        q.push(root);
        int dep=0;
        while(!q.empty()){
            int cnt=q.size();
            dep++;
            for(int i=1;i<=cnt;i++){
                TreeNode* t=q.front();q.pop();
                int qq=0;
                if(t->left) q.push(t->left);
                else qq++;
                if(t->right) q.push(t->right);
                else qq++;
                if(qq==2) return dep;
            }
        }
        return dep;
    }
};
//[2,null,3,null,4,null,5,null,6] =>5

【力扣总结】一口气刷完二叉树层次遍历的十道题（C++代码）

C/C++/C#相关栏目本月热门文章