代码随想录第15天：二叉树-创新互联

一、层序遍历

层序遍历，是按照层数从低到高，同一层从左到右遍历。在这里采用递归法是无法做到的，观察遍历的特点，这里需再加一个队列来实现。

天津网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作，到程序开发，运营维护。创新互联公司2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。

在将一层一层的二叉树节点放入队列以及弹出队列的操作中，需要记录和知道弹出的个数size。

具体思路和步骤如代码：

102.二叉树的层序遍历 #力扣题目链接

class Solution {
public:
    vector>levelOrder(TreeNode* root) {
        queueque;
        vector>result; 
        if(root != NULL)  que.push(root);        //弹入根节点
        while(!que.empty()){
            int size = que.size();              //记录size个数
            vectorvec;                    //记录某一层的结果
            while(size--){
                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(result.begin(), result.end());

199.二叉树的右视图#力扣题目链接

这道题的核心思想：就是将每一层弹出的最后一个放入结果数组中，就可以了。

class Solution {
public:
    vectorrightSideView(TreeNode* root) {
        queueque;
        vectorresult; 
        if(root != NULL)  que.push(root);        //弹入根节点
        while(!que.empty()){
            int size = que.size();              //记录size个数
            while(size--){
                TreeNode* node = que.front();  //获取要弹出的节点
                que.pop();                      //队列弹出
                if(size == 0){
                    result.push_back(node->val);       //最后一个弹出的放入结果数组即可
                }
                if(node->left) que.push(node->left);   //获取这个节点的左孩子
                if(node->right) que.push(node->right); //获取这个节点的右孩子
            }
        }
        return result;
    }
};

637.二叉树的层平均值 #力扣题目链接

这一道题的思路：在每一层的元素弹出时，记录下来并进行加和，在每一层弹出结束后将再将平均数放到result数组中即可。

class Solution {
public:
    vectoraverageOfLevels(TreeNode* root) {
        double sum = 0;    //记录求和
        vectorresult;
        queueque;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            double count = 0;               //记录某一层的元素个数
            double sum = 0;                 //记录所有数的加和
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                count++;
                sum += node->val;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
        }
            result.push_back(sum / count);  //将每一层的平均数放到数组里
        }
        return result;
    }
};

429.N叉树的层序遍历#力扣题目链接

n叉树和二叉树的层序遍历区别不大，这里将left、right变换成children[i]就可以了。

class Solution {
public:
    vector>levelOrder(Node* root) {
        queueque;
        vector>result; 
        if(root != NULL)  que.push(root);        //弹入根节点
        while(!que.empty()){
            int size = que.size();              //记录size个数
            vectorvec;                    //记录某一层的结果
            while(size--){
                Node* node = que.front();  //获取要弹出的节点
                que.pop();                      //队列弹出
                vec.push_back(node->val);       //将弹出的节点数值放入数组中
                for(int i = 0; i< node->children.size(); i++){
                    if(node->children[i]) que.push(node->children[i]);
                }
            }
            result.push_back(vec);              //将一层的数组放入到结果中
        }
        return result;
    }
};

515.在每个树行中找大值 #力扣题目链接

这道题，在每层进行比较即可获得大值即可。

class Solution {
public:
    vectorlargestValues(TreeNode* root) {
        queueque;
        vectorresult; 
        if(root != NULL)  que.push(root);        //弹入根节点
        while(!que.empty()){
            int size = que.size();              //记录size个数
            int max = INT32_MIN;                        //记录大值
            while(size--){
                TreeNode* node = que.front();  //获取要弹出的节点
                que.pop();                      //队列弹出
                if(node->val >max){                    //进行数值的比较，获得大值
                    max = node->val;
                }
                if(node->left) que.push(node->left);   //获取这个节点的左孩子
                if(node->right) que.push(node->right); //获取这个节点的右孩子
            }
            result.push_back(max);   
        }
        return result;
    }
};

116.填充每个节点的下一个右侧节点指针#力扣题目链接

这里类似于链表操作，记录好上一个元素nodePre即可，之后将next指针指向下一个元素即可。

class Solution {
public:
    Node* connect(Node* root) {
        queueque;
        if(root != NULL)  que.push(root);        //弹入根节点
        while(!que.empty()){
            int size = que.size();              //记录size个数
            Node* nodePre;
            Node* node;
            for(int i = 0; inext = node;
                    nodePre = nodePre->next;
                }
                if(node->left) que.push(node->left);   //获取这个节点的左孩子
                if(node->right) que.push(node->right); //获取这个节点的右孩子
            }
            nodePre->next = NULL;
        }
        return root;
    }
};

117.填充每个节点的下一个右侧节点指针2#力扣题目链接

解题逻辑和116一模一样。

104.二叉树的大深度#力扣题目链接

在遍历的同时，记录层数即可。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queueque;
        int result = 0;                          //记录层数
        if(root != NULL)  que.push(root);        //弹入根节点
        while(!que.empty()){
            int size = que.size();              //记录size个数
            while(size--){
                TreeNode* node = que.front();  //获取要弹出的节点
                que.pop();                      //队列弹出
                if(node->left) que.push(node->left);   //获取这个节点的左孩子
                if(node->right) que.push(node->right); //获取这个节点的右孩子
            }
            result++;
        }
        return result;
    }
};

111.二叉树的最小深度#力扣题目链接

判断条件：当左右孩子为空时，说明到遍历的最低点了。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int result = 0;
        queueque;
        que.push(root);
        while(!que.empty()) {
            int size = que.size();
            result++; // 记录最小深度
            for (int i = 0; i< size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
                if (!node->left && !node->right) { // 当左右孩子都为空的时候
                    return result;
                }
            }
        }
        return result;
    }
};

二、翻转二叉树

题目：#力扣题目链接

给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。

这道题解决的方法，先需要确定遍历方式，采用前序和后序遍历方式比较好，这里只需要进行左右孩子的交换即可。

class Solution {
public:
    void traversal(TreeNode *cur, vector& dep){           //前序遍历
        if(cur == NULL) return;
        dep.push_back(cur->val);        //中
        swap(cur->left, cur->right);                //交换左右孩子
        traversal(cur->left, dep);      //左
        traversal(cur->right, dep);     //右
    }
    TreeNode* invertTree(TreeNode* root) {
        vectorresult;
        traversal(root, result);            
        return root;
    }
};

三、对称二叉树

题目：#力扣题目链接

给你一个二叉树的根节点 root，检查它是否轴对称。

这道题判断是二叉树是否为对称二叉树，即左右孩子是否可以翻转不变，体现在外侧节点和内侧节点是否相等。

所以需要不停的判断左右孩子的信息，之后返回到根节点，这里采用遍历方式就应该只能采取后序遍历。

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right){
        //这里判断条件需要理解透彻，容易出错
        if(left == NULL && right != NULL) return false;
        else if(left != NULL && right == NULL) return false;
        else if(left == NULL && right == NULL) return true;
        else if(left->val != right->val) return false;

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        bool result = outside && inside;
        return result;
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return compare(root->left, root->right);
    }
};

四、总结和收获

在这一章节，需要我们去了解二叉树几种遍历方式的特点，并在实现过程中有意识的去分析采用那种遍历方式。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：代码随想录第15天：二叉树-创新互联
分享网址：http://scyanting.com/article/deehho.html

代码随想录第15天：二叉树-创新互联

其他资讯