如何求二叉树的最大深度和最小深度？

简化版

最大深度 = 左右子树最大深度的较大者 + 1，一行递归搞定：max(左, 右) + 1。最小深度有个坑：不能直接 min(左, 右) + 1——当一个孩子为空时，空的那侧不算路径，要走非空的那侧。求最小深度用 BFS 更好，遇到第一个叶子节点所在层就是答案，可以提前返回。

详细版

最大深度（后序递归）：

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

最小深度（注意单边为空的情况）：

int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null)  return minDepth(root.right) + 1;  // 只有右子树
    if (root.right == null) return minDepth(root.left) + 1;   // 只有左子树
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;  // 两边都有
}

最小深度的坑：最小深度是「根到最近叶子节点的路径」。如果一个节点只有右孩子（左为空），它自己不是叶子，最小深度必须往右走，而不能因为左边是 0 就返回 1。直接写 min(左,右)+1 会错。

完整版教学

一、深度/高度的定义

深度（depth）：从根到某节点的边数（或节点数），根的深度是 0（或 1，看约定）。
高度（height）：从某节点到最远叶子的边数。
树的最大深度 = 根的高度 = 树的层数。这几个概念在「求整棵树多高」时是一回事。

本题的「最大深度」指整棵树的层数（节点数口径，空树为 0、只有根为 1）。

二、最大深度：后序递归

求一棵树的最大深度，需要先知道左右子树各有多深，再取较大值加上根这一层。这是典型的后序遍历（左右根）思路：先递归算出左右子树的结果，汇总到当前节点。递归出口是「空节点深度为 0」。代码就一行，是理解「树形递归」的最佳入门题。

三、最小深度为什么不能简单取 min

最小深度是「根到最近的叶子」的距离。叶子的定义是「左右孩子都为空」。问题出在只有一个孩子的节点上：

    1
     \
      2      这棵树最小深度是 2（1→2），不是 1

节点 1 的左子树为空、右子树深度为 1。如果写 min(左=0, 右=1) + 1 = 1，就错了——因为 1 不是叶子，不能在它这里就停。正确逻辑是：哪边孩子为空，就不能走那边，必须走非空的那边。只有当两个孩子都存在时，才取两者的最小值。

四、用 BFS 求最小深度更高效

递归 DFS 求最小深度要遍历所有节点。而 BFS 层序遍历天然更适合求最小深度：一层层往下扩展，遇到的第一个叶子节点，它所在的层数就是最小深度，此时立即返回，不用再往下探。

int minDepth(TreeNode root) {
    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    int depth = 1;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left == null && node.right == null) return depth; // 第一个叶子
            if (node.left  != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        depth++;
    }
    return depth;
}

在「树很大但浅处就有叶子」时，BFS 能提前结束，明显更快。

五、复杂度

最大深度：DFS 必须看完所有节点，O(n) 时间，O(h) 递归栈空间。
最小深度：DFS O(n)；BFS 最好情况能提前返回，最坏 O(n)，空间 O(w)。

六、常见误区与追问

问题	递归转移	关键边界
最大深度	`max(left, right) + 1`	空节点深度为 0
最小深度，左右都非空	`min(left, right) + 1`	两边都存在才取 min
最小深度，某边为空	`nonEmptyDepth + 1`	不能把空孩子当成叶子路径

易错点：最小深度要到「叶子节点」才算结束，空孩子不是叶子，也不是一条合法的根到叶路径。

误区：最小深度永远可以写成 min(left, right) + 1。 当某个孩子为空时，0 会被错误地选中，单链树会被算成 1。
误区：最大深度和最小深度只是把 max 换成 min。 最大深度可以直接取最大，最小深度必须额外处理单子树节点。
误区：BFS 求最小深度也要遍历完整棵树。 BFS 按层推进，第一次遇到叶子就是最小深度，可以立即停止。
追问：根节点为空时深度是多少？ 通常返回 0；只有存在根节点时，根节点所在层才算深度 1。
追问：递归空间复杂度怎么写？ O(h)，h 是树高；平衡树 O(log n)，退化链表 O(n)。
追问：最大深度能不能用 BFS？ 可以，逐层遍历并计数层数即可；DFS 写法更短，BFS 更适合和层序类变体一起讲。

七、加强记忆

最大深度 = max(左, 右) + 1（后序递归，空节点为 0）。最小深度有坑：它是「根到最近叶子」，某个孩子为空时必须走非空那侧，不能直接 min(左,右)+1（否则单边树会算错）。求最小深度用 BFS 更优——遇到第一个叶子所在层即答案、可提前返回。都是 O(n) 时间。

简化版

详细版