104.二叉树的最大深度

给定一个二叉树，找出其最大深度。

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

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

示例：
给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

针对二叉树的结构而言，从下到上的递归很难想出来

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    // 定义一个公共方法 maxDepth 来计算二叉树的最大深度，接收树的根节点作为参数。
    public int maxDepth(TreeNode root) {
        // 如果根节点为空，说明树是空的，因此其深度为0。
        if (root == null) {
            return 0;
        } else {
            // 如果根节点不为空，递归计算根节点的左子树的最大深度。
            int leftHeight = maxDepth(root.left);
            // 递归计算根节点的右子树的最大深度。
            int rightHeight = maxDepth(root.right);
            // 最大深度是左右子树深度的较大值加上当前根节点自身的深度（即1层）。
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}