二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）
深度是节点到头结点的距离，高度是节点到最深叶子节点的距离，而且最大深度就是头结点的高度，所以计算头结点高度即可，采用后序遍历

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

二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）
本题要注意最小深度值得是叶子节点，所以相当于计算头结点的最小高度类似于计算最大高度，但是需要判断左右孩子节点为空的情况

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = minDepth(root.left);
        int rightHeight = minDepth(root.right);
        // 统计最小深度时不算null节点，而是到叶子节点的距离
        if (root.left == null) {
            return rightHeight + 1;
        }
        if (root.right == null) {
            return leftHeight + 1;
        }
        return Math.min(leftHeight, rightHeight) + 1;
    }
}

完全二叉树的节点个数

222. 完全二叉树的节点个数 - 力扣（LeetCode）
本题有两个解法，一种是针对所有的树采用普通的递归方法即可计算出节点数量，但因为本题是完全二叉树，可以使用其特性，判断其子树是否为完全二叉树，如果是，直接2的n次方减1即可

# 普通方法
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int countLeft = countNodes(root.left);
        int countRight = countNodes(root.right);
        return countLeft + countRight + 1;
    }
}

# 利用完全二叉树的特性
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        int leftDepth = 0;
        int rightDepth = 0;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        // 如果左右节点深度相同，那么一定是满二叉树（和完全二叉树的特性有关）
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}