立志重刷代码随想录60天冲冲冲！！——第十四天

226.翻转二叉树

前、后序遍历。就增加了交换位置

交换每个孩子节点的位置

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return root;
        // 前序、后序可以。中序的话：左中左或右中右
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

101. 对称二叉树

外侧对比，内侧对比

class Solution {
public:
    // 收集孩子的信息，向上一级返回，需要后序（左右中）
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right != nullptr) return false;
        else if (left != nullptr && right == nullptr) return false;
        else if (left == nullptr && right == nullptr) return true;
        else if (left->val != right->val) return false;

        bool outside = compare(left->left, right->right);
        bool inside = compare(left->right, right->left);
        return outside && inside;
    }

    bool isSymmetric(TreeNode* root) {
        bool res = compare(root->left, root->right);
        return res;
    }
};

104.二叉树的最大深度

后序（左右中）计算最大高度。

1、确定返回值和参数（int和node）

2、终止条件

3、后序排列，逻辑是左右孩子最大值再➕1

class Solution {
public:
    int GetMaxHeight(TreeNode* node) {
        if (node == nullptr) return 0;
        int LeftHeight = GetMaxHeight(node->left);
        int RightHeight = GetMaxHeight(node->right);
        int Height = max(LeftHeight, RightHeight) + 1;
        return Height;
    }

    int maxDepth(TreeNode* root) {
        int height = GetMaxHeight(root);
        return height;
    }
};

111.二叉树的最小深度

处理逻辑非常重要！！

后序遍历（左右中）

左空右有，右➕1

左有右空，左➕1

左右都有，最小值➕1

class Solution {
public:
    int GetMinHeight(TreeNode* node) {
        if (node == nullptr) return 0;

        int leftheight = GetMinHeight(node->left);
        int rightheight = GetMinHeight(node->right);
        // 需要注意的地方！！！此处逻辑非常重要
        if (node->left == nullptr && node->right != nullptr) {
            return rightheight + 1;
        } else if (node->left != nullptr && node->right == nullptr) {
            return leftheight + 1;
        } else {
            int height = min(leftheight, rightheight) + 1;
            return height;
        }
    }
    
    int minDepth(TreeNode* root) {
        int height = GetMinHeight(root);
        return height;
    }
};