代码随想录算法训练营第15天 | 层序遍历 10题、226.翻转二叉树、101.对称二叉树 2

发布于 2022-11-30  459 次阅读


十道层序遍历题

102. 二叉树的层序遍历 - 力扣(LeetCode)

思路:使用队列queue来辅助解决这道题目。先把根节点放到队列中,然后每次循环开始都统计队列此时的长度size(注意是此时的长度),将队列中的元素一一弹出,同时将被弹出的元素的左右孩子推入队列,当size为0时即为一层遍历完成

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int> > ans;
        if(root == nullptr) {
            return ans;
        }
        q.push(root);
        while(!q.empty()) {
            vector<int> atmp;
            int qsize = q.size();
            while(qsize--) {
                TreeNode* tmp = q.front();
                q.pop();
                atmp.push_back(tmp->val);
                if(tmp->left)  q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
            ans.push_back(atmp);
            atmp.clear();
        }
        return ans;
    }
};

标准答案

迭代法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的
            for (int i = 0; i < size; i++) {
                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;
    }
};
递归法
class Solution {
public:
    void order(TreeNode* cur, vector<vector<int>>& result, int depth) {
        if (cur == nullptr) return;
        if (result.size() == depth) result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

107. 二叉树的层序遍历 II - 力扣(LeetCode)

思路:层序遍历一次,最后将结果数组反转即可

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root == nullptr) {
            return ans;
        }
        que.push(root);
        while(!que.empty()) {
            int qsize = que.size();
            vector<int> atmp;
            while(qsize--) {
                TreeNode* tmp = que.front();
                que.pop();
                atmp.push_back(tmp->val);
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
            }
            ans.push_back(atmp);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

199. 二叉树的右视图 - 力扣(LeetCode)

思路:进行层序遍历,每次遍历到每一层的最后一个就加入结果数组

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> ans;
        if(root == nullptr) {
            return ans;
        }
        que.push(root);
        while(!que.empty()) {
            int qsize = que.size();
            while(qsize--) {
                TreeNode* tmp = que.front();
                que.pop();
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
                if(qsize == 0) {
                   ans.push_back(tmp->val); 
                }
            }
        }
        return ans;
    }
};

637. 二叉树的层平均值 - 力扣(LeetCode)

思路:层序遍历二叉树,计算每一层的平均值

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        queue<TreeNode*> que;
        if(root == nullptr) {
            return ans;
        }
        que.push(root);
        while(!que.empty()) {
            double ave = 0;
            int qsize = que.size();
            int cnt = qsize;
            while(qsize--) {
                TreeNode* tmp = que.front();
                que.pop();
                ave += tmp->val;
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
            }
            ans.push_back(ave / cnt);
        }
        return ans;
    }
};

429. N 叉树的层序遍历 - 力扣(LeetCode)

思路:和层序遍历思路一样,不过遍历的时候要将所有子树都加入队列

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int> > ans;
        queue<Node*> que;
        if(root == nullptr) {
            return ans;
        }
        que.push(root);
        while(!que.empty()) {
            vector<int> atmp;
            int qsize = que.size();
            while(qsize--) {
                Node* tmp = que.front();
                atmp.push_back(tmp->val);
                que.pop();
                int nsize = tmp->children.size();
                for(int i = 0; i < nsize; ++i) {
                    if(tmp->children[i] != nullptr) {
                        que.push(tmp->children[i]);
                    }
                }
            }
            ans.push_back(atmp);
        }
        return ans;
    }
};

515. 在每个树行中找最大值 - 力扣(LeetCode)

思路:层序遍历二叉树,找出每层的最大值即可

注意:数据可能是负的

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> que;
        if(root == nullptr) {
            return ans;
        }
        que.push(root);
        while(!que.empty()) {
            long long mmax = -(2e10 + 10);
            int qsize = que.size();
            while(qsize--) {
                TreeNode* tmp = que.front();
                que.pop();
                if(tmp->val > mmax) {
                    mmax = tmp->val;
                }
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
            }
            ans.push_back(mmax);
        }
        return ans;
    }
};

116. 填充每个节点的下一个右侧节点指针 - 力扣(LeetCode)

思路:层序遍历二叉树,如果遍历到的节点不是最后一个就指向下一个节点,否则指向NULL

注意:要注意判断的方法,当qsize == 0时说明是末尾

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root == NULL) {
            return root;
        }
        que.push(root);
        while(!que.empty()) {
            int qsize = que.size();
            while(qsize--) {
                Node* tmp = que.front();
                que.pop();
                if(!que.empty()) {
                    Node* tmp2 = que.front();
                    if(qsize == 0) {
                        tmp->next = NULL;
                    }
                    else {
                        tmp->next = tmp2;
                    }
                }
                else {
                    tmp->next = NULL;
                }
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
            }
        }
        return root;
    }
};

117. 填充每个节点的下一个右侧节点指针 II - 力扣(LeetCode)

思路:和上道题目一模一样,直接复制粘贴代码就过了

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if(root == NULL) {
            return root;
        }
        que.push(root);
        while(!que.empty()) {
            int qsize = que.size();
            while(qsize--) {
                Node* tmp = que.front();
                que.pop();
                if(!que.empty()) {
                    Node* tmp2 = que.front();
                    if(qsize == 0) {
                        tmp->next = NULL;
                    }
                    else {
                        tmp->next = tmp2;
                    }
                }
                else {
                    tmp->next = NULL;
                }
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
            }
        }
        return root;
    }
};

104. 二叉树的最大深度 - 力扣(LeetCode)

思路:层序遍历二叉树,每遍历一层深度就加一

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> q;
        int ans = 0;
        if(root == nullptr) {
            return ans;
        }
        q.push(root);
        while(!q.empty()) {
            ans++;
            int qsize = q.size();
            while(qsize--) {
                TreeNode* tmp = q.front();
                q.pop();
                if(tmp->left)  q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
        }
        return ans;
    }
};

111. 二叉树的最小深度 - 力扣(LeetCode)

思路:层序遍历二叉树,每遍历一层计数加一,如果遇到某一个节点没有左右子树则直接返回答案

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> q;
        int ans = 0;
        if(root == nullptr) {
            return ans;
        }
        q.push(root);
        while(!q.empty()) {
            ans++;
            int qsize = q.size();
            while(qsize--) {
                TreeNode* tmp = q.front();
                q.pop();
                int flag = 0;
                if(tmp->left) {
                      q.push(tmp->left);
                }
                else {
                    flag++;
                }
                if(tmp->right) {
                      q.push(tmp->right);
                }
                else {
                    if(flag == 1) {
                        return ans;
                    }
                }
            }
        }
        return ans;
    }
};

226. 翻转二叉树 - 力扣(LeetCode)

思路:层序遍历二叉树,每次都将遍历到的节点的左右子树相互交换

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if(root == nullptr) {
            return root;
        }
        que.push(root);
        while(!que.empty()) {
            int qsize = que.size();
            while(qsize--) {
                TreeNode* tmp = que.front();
                que.pop();
                if(tmp->left && tmp->right) {
                    TreeNode* node = tmp->left;
                    tmp->left = tmp->right;
                    tmp->right = node;
                }
                else if(tmp->left == nullptr && tmp->right) {
                    tmp->left = tmp->right;
                    tmp->right = nullptr;
                }
                else if(tmp->left && tmp->right == nullptr) {
                    tmp->right = tmp->left;
                    tmp->left = nullptr;
                }
                if(tmp->left) {
                    que.push(tmp->left);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
            }
        }
        return root;
    }
};

标准答案

递归法(前序遍历)

//时间复杂度O(n),空间复杂度O(n)
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;
    }
};

递归法(中序遍历)

//时间复杂度O(n),空间复杂度O(n)
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;
    }
};

迭代法:深度优先遍历(前序遍历)

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        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;
    }
};

迭代法:广度优先遍历(层序遍历)

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right); // 节点处理
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return root;
    }
};

迭代法(统一中序遍历)

 //时间复杂度O(n),空间复杂度O(n)
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);  // 右
                st.push(node);                          // 中
                st.push(NULL);
                if (node->left) st.push(node->left);    // 左

            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

101. 对称二叉树 - 力扣(LeetCode)

思路:层序遍历二叉树,得到序列以后逐层对比是否对称,如果全部对称则返回true,否则返回false

注意:遇到空节点要给一个填充值

我的AC代码

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> que;
        if(root->left == nullptr && root->right == nullptr) {
            return true;
        }
        que.push(root);
        while(!que.empty()) {
            int qsize = que.size();
            vector<int> atmp;
            while(qsize--) {
                TreeNode* tmp = que.front();
                que.pop();
                if(tmp == nullptr) {
                    atmp.push_back(9999);
                    continue;
                }
                else {
                    atmp.push_back(tmp->val);
                }
                if(tmp->left) {
                    que.push(tmp->left);
                }
                else {
                    que.push(nullptr);
                }
                if(tmp->right) {
                    que.push(tmp->right);
                }
                else {
                    que.push(nullptr);
                }
            }
            ans.push_back(atmp);
        }
        for(auto a : ans) {
            int asize = a.size();
            int left = 0;
            int right = asize - 1;
            while(left < right) {
                if(a[left] != a[right]) {
                    return false;
                }
                left++;
                right--;
            }
        }
        return true;
    }
};

标准答案

递归法

//时间复杂度O(n),空间复杂度O(n)
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 isSame = outside && inside;                    // 左子树:中、 右子树:中 (逻辑处理)
        return isSame;

    }
    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* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空,此时说明是对称的
                continue;
            }

            // 左右一个节点不为空,或者都不为空但数值不相同,返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};

迭代法(使用栈)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        stack<TreeNode*> st; // 这里改成了栈
        st.push(root->left);
        st.push(root->right);
        while (!st.empty()) {
            TreeNode* leftNode = st.top(); st.pop();
            TreeNode* rightNode = st.top(); st.pop();
            if (!leftNode && !rightNode) {
                continue;
            }
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            st.push(leftNode->left);
            st.push(rightNode->right);
            st.push(leftNode->right);
            st.push(rightNode->left);
        }
        return true;
    }
};