个人博客主页：http://myblog.nxx.nx.cn
代码GitHub地址：https://github.com/nx-xn2002/Data_Structure.git

Day15

226. 翻转二叉树

题目链接：
https://leetcode.cn/problems/invert-binary-tree/

题目描述：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

思路：
本题可以使用递归的思路，我们可以注意到，翻转一个二叉树后，二叉树中的所有子树其实都经过过翻转，因此可以通过递归让根节点的左右子树先进行翻转操作，然后将根节点的左指针指向右子树根节点，右指针指向左子树根节点，完成当前树的翻转。

代码实现：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.right);
        invertTree(root.left);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
}

101. 对称二叉树

题目链接：
https://leetcode.cn/problems/symmetric-tree/

题目描述：
给你一个二叉树的根节点 root ， 检查它是否轴对称。

思路：
本题也是可以使用递归来实现，当根节点为空时，可以判断这个二叉树是对称的，接下来，就是如果左右子树也满足对称，当前二叉树就是对称的。左右子树满足对称的条件则是左子树的左子树和右子树的右子树、左子树的右子树和右子树的左子树都满足对称。

代码实现：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return compare(root.left, root.right);
    }

    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return compare(left.left, right.right) && compare(left.right, right.left);
    }
}

104.二叉树的最大深度

题目链接：
https://leetcode.cn/problems/maximum-depth-of-binary-tree/

题目描述：
给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思路：
本题使用递归也很好理解，当前节点为空时，返回当前节点为根节点的树最大深度为 0。当当前节点不为空时，该树的最大深度就是左子树的最大深度和右子树最大深度的最大值加一，至此，完成递归

代码实现：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

111. 二叉树的最小深度

题目链接：
https://leetcode.cn/problems/minimum-depth-of-binary-tree/

题目描述：
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路：
本题看上去和上一题一样，但实际实现需要考虑的更多，因为最小深度的定义是从根节点到最近叶子节点的最短路径上的节点数量，我们的递归需要在叶子结点处返回结果，即左右子树都为空。

代码实现：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int res = Integer.MAX_VALUE;
        if (root.left != null) {
            res = Math.min(minDepth(root.left), res);
        }
        if (root.right != null) {
            res = Math.min(minDepth(root.right), res);
        }
        return res + 1;
    }
}