题目1：翻转二叉树

翻转一棵二叉树。

例如，给定二叉树:

 4

/
2 7
/ \ /
1 3 6 9
翻转后为:

 4

/
7 2
/ \ /
9 6 3 1
答案1：
以下是 Java 实现：

public TreeNode invertTree(TreeNode root) {
if (root == null) return null;

TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);

root.left = right;
root.right = left;

return root;

}
我们使用递归来解决这个问题。对于每个节点，我们先递归地翻转它的左子树和右子树，然后交换它们的左右节点。

时间复杂度为 O(n)，其中 n 是二叉树中的节点个数。空间复杂度为 O(h)，其中 h 是二叉树的高度。在最坏情况下，二叉树退化为链表，此时空间复杂度为 O(n)。

最小深度

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) { // 如果根节点为空，返回 0
            return 0;
        }
        if (root.left == null && root.right == null) { // 如果根节点为叶子节点，返回 1
            return 1;
        }
        if (root.left == null) { // 如果左子树为空，递归遍历右子树
            return minDepth(root.right) + 1;
        }
        if (root.right == null) { // 如果右子树为空，递归遍历左子树
            return minDepth(root.left) + 1;
        }
        // 如果左右子树都不为空，取左右子树中最小深度加 1
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) { // 如果根节点为空，返回 0
            return 0;
        }
        int leftDepth = maxDepth(root.left); // 递归遍历左子树
        int rightDepth = maxDepth(root.right); // 递归遍历右子树
        return Math.max(leftDepth, rightDepth) + 1; // 取左右子树中最大深度加 1
    }
}

平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        if (leftHeight == -1) { // 左子树不平衡，直接返回 -1
            return -1;
        }
        int rightHeight = height(root.right);
        if (rightHeight == -1) { // 右子树不平衡，直接返回 -1
            return -1;
        }
        if (Math.abs(leftHeight - rightHeight) > 1) { // 左右子树高度差大于 1，返回 -1
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1; // 返回当前节点的高度
    }
}

在这个自底向上递归的解法中，我们同样采用递归的方式计算二叉树的高度。但是，与自顶向下的递归不同的是，我们在计算左右子树的高度时，如果发现左右子树不平衡，直接返回 -1。

在递归回溯时，我们判断当前节点的左右子树高度差是否大于 1，如果大于 1，直接返回 -1。如果左右子树都平衡，返回当前节点的高度，即左右子树的最大高度加 1。如果整个二叉树是平衡二叉树，最终会返回根节点的高度，否则会返回 -1。