代码随想录算法训练营第24天（补第13天）|226.翻转二叉树， 101. 对称二叉树，104.二叉树的最大深度,111.二叉树的最小深度

226.翻转二叉树

文章链接：https://programmercarl.com/0226.翻转二叉树.html#算法公开课
题目链接：https://leetcode.cn/problems/invert-binary-tree/description/

迭代法:
这里使用了前序遍历来交换左右孩子节点

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

递归法：

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

101. 对称二叉树

文章链接：https://programmercarl.com/0101.对称二叉树.html
题目链接：https://leetcode.cn/problems/symmetric-tree/

要点：注意！分内外两层

class Solution {
public:
    bool compareLR(TreeNode*left,TreeNode*right){
        //排除空节点的情况
        if(left==NULL&&right==NULL) return true;
        else if(left!=NULL&&right==NULL) return false;
        else if(left==NULL&&right!=NULL) return false;
        //排除非空节点，但是不相等的情况
        else if(left!=NULL&&right!=NULL&&left->val!=right->val) return false;
        //最后剩下两个都是非空节点，但是相等的情况
        //每个进行比较的一对节点的后续子节点都可以分为内外两层进行比较
        return compareLR(left->left,right->right)&&compareLR(left->right,right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;
        return compareLR(root->left,root->right);
    }
};

104.二叉树的最大深度

文章链接：https://programmercarl.com/0104.二叉树的最大深度.html
题目链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
};

111.二叉树的最小深度

文章链接：https://programmercarl.com/0111.二叉树的最小深度.html#思路
题目链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL) return 0;
        if(root->left!=NULL&&root->right==NULL) return 1+minDepth(root->left);
        if(root->left==NULL&&root->right!=NULL) return 1+minDepth(root->right);
        if(root->left!=NULL&&root->right!=NULL) return 1+min(minDepth(root->left),minDepth(root->right));
        return 1; 
    }
};

实际上后两种情况可以合并：
修改后的代码：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL) return 0;
        if(root->left!=NULL&&root->right==NULL) return 1+minDepth(root->left);
        if(root->left==NULL&&root->right!=NULL) return 1+minDepth(root->right);
        return 1+min(minDepth(root->left),minDepth(root->right));
    }
};