二叉树最大深度与最小深度-一文搞懂递归的精髓与陷阱

二叉树的最大深度

在这里插入图片描述

代码逻辑

当遇到空节点时返回深度 0 作为递归的终止条件，否则分别递归计算左右子树的深度，取两者中的较大值后加 1（这个 +1 代表当前节点本身占据的一层），最终得到以当前节点为根的子树的最大深度。

代码实现

1
2
3


public static int maxDepth(TreeNode root) {
    return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

二叉树的最小深度

在这里插入图片描述

代码逻辑

代码通过三层判断来确保找到真正的最小深度：

首先判断空树直接返回 0，其次判断叶子节点（左右子树都为空）直接返回 1，最后对于有子树的节点，将左右深度初始化为 Integer.MAX_VALUE，只有当某侧子树存在时才递归计算其真实深度，这样在取 min 时会自动忽略不存在的子树（因为 MAX_VALUE 必然更大），最终加 1 得到当前节点的最小深度。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public int minDepth(TreeNode root) {
    if (root == null) {
        // 空树深度为 0
        return 0;
    }
    if (root.left == null && root.right == null) {
        // 当前节点是叶子节点
        return 1;
    }
    
    int ldeep = Integer.MAX_VALUE;
    int rdeep = Integer.MAX_VALUE;
    
    if (root.left != null) {
        ldeep = minDepth(root.left);
    }
    if (root.right != null) {
        rdeep = minDepth(root.right);
    }
    
    return Math.min(ldeep, rdeep) + 1;
}