代码随想录算法训练营第23期day14|二叉树层序遍历、226.翻转二叉树、101. 对称二叉树

目录

一、二叉树层序遍历

非递归法

递归法

相关题目（10题）

 二、（leetcode 226）翻转二叉树

递归法

层序遍历

深度优先遍历

1）非统一写法——前序遍历

2） 统一写法——前序遍历

三、（leetcode 101）对称二叉树

递归法

迭代法

1）使用队列

2）使用栈

---

一、二叉树层序遍历

借用队列实现，因为队列先进先出，符合层序遍历逻辑

非递归法

class Solution {
public:
    vectorint>> levelOrder(TreeNode* root) {
        queue que;
        if (root != NULL) que.push(root);
        vectorint>> 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, vectorint>>& 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);
    }
    vectorint>> levelOrder(TreeNode* root) {
        vectorint>> result;
        int depth = 0;
        order(root, result, depth);
        return result;
    }
};

相关题目（10题）

• 102.二叉树的层序遍历(opens new window)
• 107.二叉树的层次遍历II(opens new window)
• 199.二叉树的右视图(opens new window)
• 637.二叉树的层平均值(opens new window)
• 429.N叉树的层序遍历(opens new window)
• 515.在每个树行中找最大值(opens new window)
• 116.填充每个节点的下一个右侧节点指针(opens new window)
• 117.填充每个节点的下一个右侧节点指针II(opens new window)
• 104.二叉树的最大深度(opens new window)
• 111.二叉树的最小深度

 二、（leetcode 226）翻转二叉树

力扣题目链接

状态：递归法、层序遍历AC，深度优先遍历还需回顾（原始代码就没有看的很清楚）

递归法

前序、后序遍历都可以，中序不行

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);         // 左
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

层序遍历

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue 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;
    }
};

深度优先遍历

1）非统一写法——前序遍历

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack 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;
    }
};

2） 统一写法——前序遍历

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack 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;
    }
};

三、（leetcode 101）对称二叉树

力扣题目链接

状态：递归法顺利AC，迭代法中使用栈的思路清楚并AC，使用队列的部分有点乱

递归法

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;
        else return compare(left->left, right->right) && compare(left->right, right->left);
 
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

迭代法

1）使用队列

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue 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;
    }
};

2）使用栈

把左右两个子树要比较的元素顺序放进一个容器，然后成对成对的取出来进行比较

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        stack 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;
    }
};