首页 > 编程语言 >代码随想录算法训练营第十四天 层序遍历 | lc226.翻转二叉树 | lc101.对称二叉树 2

代码随想录算法训练营第十四天 层序遍历 | lc226.翻转二叉树 | lc101.对称二叉树 2

时间：2023-02-20 20:33:14浏览次数：34  
标签：node right 随想录 第十四天 que 二叉树 push root left

二叉树广度优先搜索

lc102 二叉树的层序遍历

二叉树的层序遍历可以依靠队列来完成，使用队列的大小来记录每一层的大小，一层遍历完毕时下一层的节点也已经添加到了队列里，此时更新层大小，继续遍历直到队列为空

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> level;
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                level.push_back(node->val);
            }
            result.push_back(level);
        }
        return result;
    }
};

lc107 二叉树的层序遍历II

只需要最后反转一下返回数组

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> level;
            while(size--){
                TreeNode* cur = que.front();
                que.pop();
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
                level.push_back(cur->val);
            }
            result.push_back(level);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

lc199 二叉树的右视图

相当于每次先加入右子节点，然后返回每层的第一个节点
也可以继续从左到右层序遍历，返回每层最后一个节点即可

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> que;
        if(root) que.push(root);
        while(!que.empty()){
            int size = que.size();
            bool found = false;
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(!found){
                    result.push_back(node->val);
                    found = true;
                }
                if(node->right) que.push(node->right);
                if(node->left) que.push(node->left);
            }
        }
        return result;
    }
};

lc637 二叉树的层平均值

还是层序遍历，只是拿到每层的数据之后算平均数即可

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            double sum = 0;
            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);
                sum += node->val;
            }
            result.push_back(sum / size);
        }
        return result;
    }
};

lc429 N叉树的层序遍历

思路与二叉树层序遍历完全一致， 唯一的不同点是该题目中使用节点列表储存子节点，需要在弹出节点时将其子节点列表遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        if(root != NULL) que.push(root);
        vector<vector<int>> result;
        while(!que.empty()){
            int size = que.size();
            vector<int> level;
            while(size--){
                Node* node = que.front();
                que.pop();
                level.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(level);
        }
        return result;
    }
};

lc515 在每个树行中找最大值

本题目与之前的求平均值类似，得到每一行的值后只需要记录最大值即可

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        vector<int> result;
        while(!que.empty()){
            int size = que.size();
            int maxval = INT_MIN;
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                maxval = node->val > maxval ? node->val : maxval;
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(maxval);
        }
        return result;
    }
};

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

依然使用层序遍历，注意size在能记录是否到达了一层最后，一层内最后一次循环时，size会被减成0，可以以此来判断是否需要对next进行填充。因为我们添加子节点时从左向右填充，所以在弹出当前节点后，需要填充next时，将next填充为当前队列的首元素即可

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                Node* node = que.front();
                que.pop();
                if(size > 0){
                    node->next = que.front();
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

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

不再提供完美二叉树，不过对我们的解法似乎没有任何影响，使用与lc116 完全一致的代码即可通过。

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                Node* node = que.front();
                que.pop();
                if(size > 0){
                    node->next = que.front();
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
};

lc104 二叉树的最大深度

这道题目最难的地方是想到可以使用广度优先搜索或者层级遍历来进行迭代法

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        int count = 0;
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            count++;
        }
        return count;
    }
};

lc111 二叉树的最小深度

在寻找最大深度的基础上，需要增加提前遇到叶（即没有子节点的节点）时进行返回

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        int count = 0;
        while(!que.empty()){
            int size = que.size();
            count++;
            while(size--){
                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 count; //one leaf was found
                }
            }
        }
        return count;
    }
};

lc226 翻转二叉树

翻转二叉树其实就是交换每一个节点的左右子节点（交换指针）

递归法

遍历时，前序和后序比较方便。使用中序时需要注意翻转后的右会变为左。

递归前序

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

递归后序

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};

递归中序

递归中序即左 中 右顺序，交换完左边后，处理中间，此时左边会被换到右边，此时的右边其实就是刚刚交换过的左边，所以相当于原二叉树的左侧被放到了右边并且交换了两次，而右侧只是被放到了左边，没有进行交换。

所以处理完 中 后，应该继续处理的是当前的左，即原来的右。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        invertTree(root->left);
        swap(root->left,root->right);
        invertTree(root->left);
        return root;
    }
};

迭代法

本题深度优先遍历的迭代法是使用栈来模拟递归，深度优先遍历分为统一的写法和普通写法。统一写法即前中后序之间比较相似，一般写法前序和中序区别较大，以下附上前中后序的一般写法，前序的统一写法 以及 广度（层序遍历）写法。

具体可以参照各遍历方式的题目，只需要把添加到返回数组的步骤改为交换左右子节点即可

前序普通

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if(root != NULL) st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            st.pop();
            swap(node->left,node->right);           //中
            if(node->right) st.push(node->right);   //右
            if(node->left) st.push(node->left);     //左
        }
        return root;
    }
};

后序普通

在遍历时后续普通其实与前序基本一致，交换了左右的顺序，并最后反转了数组，本题没有数组需要返回，只交换左右意义不大

中序普通

注意中序普通中使用了指针来记录当前处理位置，与递归法中的中序面临同样的问题，所以交换完后的左子节点其实是原来的右子节点

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur || !st.empty()){
            if(cur){
                st.push(cur);
                cur = cur->left; //左
            }
            else{
                cur = st.top(); //中
                st.pop();
                swap(cur->left,cur->right);
                cur = cur->left;
            }
        }
        return root;
    }
};

前序统一

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if(root != NULL) st.push(root);
        while(!st.empty()){
            TreeNode* node = st.top();
            if(node != NULL){
                st.pop();
                if(node->right) st.push(node->right); //右
                if(node->left) st.push(node->left); //左
                st.push(node);                      //中
                st.push(NULL);
            }
            else{
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left,node->right);
            }
        }
        return root;
        
    }
};

注意中序统一写法与之前不同，没有使用指针记录处理位置，所以不需要右变成左

广度优先 层序遍历

广度优先比较符合题意也比较好写，就是交换每一个节点的左右子节点

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                swap(node->left,node->right);
            }
        }
        return root;
    }
};

lc101 对称二叉树

本题目可以分为递归法与迭代法

递归法

递归法只能使用后序遍历，因为只有知道子节点是否对称，才能返回给父节点

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);
    }
};

迭代法

迭代法可以使用队列或栈，成对加入容器并弹出比较

队列

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);

        while(!que.empty()){
            TreeNode* left = que.front();
            que.pop();
            TreeNode* right = que.front();
            que.pop();
            if(left == NULL && right == NULL){
                continue;
            }
            //左右不同时为空，或左右值不相等
            if(!left || !right || (left->val != right->val)){
                return false;
            }
            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};

栈

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        stack<TreeNode*> st;
        st.push(root->right);
        st.push(root->left);
        
        while(!st.empty()){
            TreeNode* left = st.top();
            st.pop();
            TreeNode* right = st.top();
            st.pop();
            if(left == NULL && right == NULL){
                continue;
            }
            //左右不同时为空，或左右值不相等
            if(!left || !right || (left->val != right->val)){
                return false;
            }
            st.push(right->right);
            st.push(left->left);
            st.push(right->left);
            st.push(left->right);
        }
        return true;
    }
};

层序遍历

确实可以尝试使用层序遍历然后判断一层是否对称，使用-101来表示空是因为题目中树里正常情况下最小值是-100。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        if(root->left == NULL && root->right == NULL) return true;
        if(!root->left || !root->right) return false;
        queue<TreeNode*> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()){
            int size = que.size();
            vector<int> level;
            while(size--){
                TreeNode* node = que.front();
                que.pop();
                if(node == NULL){
                    level.push_back(-101);
                }
                else{
                    level.push_back(node->val);
                    que.push(node->left);
                    que.push(node->right);
                }
            }
            if(level.size() % 2 != 0) return false;
            for(int i = 0; i < level.size()/2; i++){
                if(level[i] != level[level.size()-1-i]){
                    return false;
                }
            }
        }
        return true;
    }
};

标签：node,right,随想录,第十四天,que,二叉树,push,root,left
From： https://www.cnblogs.com/frozenwaxberry/p/17138828.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99