投稿
  1. 首页
  2. C

【代码随想录】——二叉树层序遍历

iphone铃声格式 • 2022-6-14 • C • 阅读 62

【代码随想录】——二叉树层序遍历,第1张

之前介绍的是二叉树的深度优先遍历，接着是二叉树的另外一种遍历方式——层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

102. 二叉树的层序遍历

方法一：

/**
 * 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> levelOrder(TreeNode* root) {
        vector> res;
        queue que;
        if(root==NULL) return res;
        que.push(root);

        while(!que.empty()){
            int size=que.size();//变化的size，因为每次的que都在变化
            vector path;//每完成一层for循环，重新定义一个新path，不用清除之前的数据，满足了[[3],[9,20]]这种要求
            //一次for循环，填充每一个path
            for(int i=0;ival);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            } 
            //for循环之后，将填好的path放进res中
            res.push_back(path);
        }
        return res;
    }
};

方法二：相较于方法一，不同之处在于：for循环将每层填好的path放进res中之后，用path.clear()清除每层的path，就不用每一层申请一个新path。

/**
 * 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> levelOrder(TreeNode* root) {
        vector path;
        vector> res;
        queue que;
        if(root==NULL) return res;
        que.push(root);

        while(!que.empty()){
            int size=que.size();//变化的size，因为每次的que都在变化
            //一次for循环，填充每一个path
            for(int i=0;ival);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            } 
            res.push_back(path);//for循环之后，将每层填好的path放进res中
            path.clear();//清除每层的path
        }
        return res;
    }
};

107. 二叉树的层序遍历 II

该题与上题的不同之处在于：自底向上的层序遍历

其实只需要在上题的基础上，做一个reverse的 *** 作即可。

/**
 * 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> levelOrderBottom(TreeNode* root) {
        vector path;
        vector> res;
        queue q;
        if(root==NULL) return res;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;ival);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(path);
            path.clear();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

199. 二叉树的右视图

该题也是层序遍历的变形。其实就是将每层的最后一个元素放进res中返回即可 

/**
 * 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 rightSideView(TreeNode* root) {
        vector path;
        vector res;
        queue q;
        if(root==NULL) return res;
        q.push(root);

        while(!q.empty()){
            int size=q.size();
            for(int i=0;ival);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(path[path.size()-1]);
        }
        return res;
    }
};

 637. 二叉树的层平均值

 在每一层for循环的时候将sum统计出来，然后在for循环结束之后就求平均值，将平均值放进res中。

/**
 * 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 averageOfLevels(TreeNode* root) {
        vector res;
        queueq;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            double sum=0;
            for(int i=0;ival;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(sum/size);
        }
        return res;
    }
};

 429. N 叉树的层序遍历

和二叉树的层序遍历区别在于：二叉树只有两个孩子节点，判断左右孩子不为空即可让他们入队。而N叉树有n个孩子节点，就需要借助for循环将每一个孩子判空然后入队。

 for(int j=0;jchildren.size();j++){//将node节点的孩子节点依次放进队列中
                    if(node->children[j]) q.push(node->children[j]);
                }
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector> levelOrder(Node* root) {
        vector> res;
        vector path;
        queue q;
        if(root==NULL) return res;
        q.push(root);

        while(!q.empty()){
            int size=q.size();
            for(int i=0;ival);
                for(int j=0;jchildren.size();j++){//将node节点的孩子节点依次放进队列中
                    if(node->children[j]) q.push(node->children[j]);
                }
            }
            res.push_back(path);
            path.clear();
        }
        return res;
    }
};

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

 层序遍历大框架，每层for循环的时候，比较求出最大值，每层for循环结束后，将最大值放进res。

/**
 * 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 largestValues(TreeNode* root) {
        vector res;
        queue q;
        if(root==NULL) return res;
        q.push(root);

        while(!q.empty()){
            int size=q.size();
            int max=INT_MIN;
            for(int i=0;ival>max) max=node->val;
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(max);
        }
        return res;
    }
};

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

每层for循环，重新定义size，nodepre，node

在单层遍历时（包括i=0,i>0时）记录本层的头部节点，然后在遍历的时候（i>0时）让前一个节点指向本节点就可以了

然后每层for循环结束，本层最后一个节点指向NULL

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue q;
        if(root!=NULL) q.push(root);

        while(!q.empty()){
            //每层for循环，重新定义size，nodepre，node
            int size=q.size();
            Node* nodepre;
            Node* node;

            for(int i=0;inext=node;//本层前一个节点指向本节点
                    nodepre=nodepre->next;
                } 
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            nodepre->next=NULL;//每层for循环结束，本层最后一个节点指向NULL
        }
        return root;
    }
};

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

这道题是二叉树，上一道题是完美二叉树，其实没有任何差别，一样的代码一样的逻辑一样的味道

每层for循环，重新定义size，nodepre，node

在单层遍历时（包括i=0,i>0时）记录本层的头部节点，然后在遍历的时候（i>0时）让前一个节点指向本节点就可以了

然后每层for循环结束，本层最后一个节点指向NULL

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        queue q;
        if(root!=NULL) q.push(root);

        while(!q.empty()){
            int size=q.size();
            Node* nodePre;
            Node* node;
            for(int i=0;inext=node;
                    nodePre=nodePre->next;
                }
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            nodePre->next=NULL;
        }
        return root;
    }
};

 104. 二叉树的最大深度

最大深度即是二叉树的层数，层序遍历获得层数即可。

利用层序遍历的大框架，每层for循环结束之后sum++

最终while结束后，返回sum 

/**
 * 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:
    int maxDepth(TreeNode* root) {
        int sum=0;
        queue q;
        if(root!=NULL) q.push(root);
        while(!q.empty()){
            int size=q.size();
            for(int i=0;ileft) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            sum++;
        }
        return sum;

    }
};

111. 二叉树的最小深度

层序遍历大框架，当node的左右孩子均为空的时候，说明到了最低点的一层，直接返回深度

/**
 * 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:
    int minDepth(TreeNode* root) {
        queue q;
        int mindepth=0;
        if(root!=NULL) q.push(root);
        while(!q.empty()){
            int size=q.size();
            mindepth++;
            for(int i=0;ileft) q.push(node->left);
                if(node->right) q.push(node->right);
                if(node->left==NULL && node->right==NULL) return mindepth;//当左右节点都为空，说明到了最低点的一层，直接返回
            }
        }
        return mindepth;
    }
};

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1353616.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
iphone铃声格式 iphone铃声格式 一级用户组
0 0
上一篇 2022-06-14
下一篇 2022-06-14

发表评论

登录后才能评论

评论列表（0条）

保存