二叉树的最小深度 图解题解

这道题到底在问什么

输入

[7,4,9,2,null,6,13,1,3,null,null,8,null,15]

输出

4

最优解：一步一步想明白

1. 3这就是最小深度和最大深度最大的不同。最大深度里空侧取 0 无所谓(反正要 max)；但最小深度求的是到最近叶子，空子树根本没有叶子，不能把它当成「0 步可达的叶子」。所以单孩子节点必须绕开空侧、走有孩子那边。下面逐节点看。
2. 4后序 DFS 起点 = 根 7先看清这棵树：根是 7。树里有几个只有一个孩子的节点，它们不是叶子。接下来从根出发做后序 DFS——扎到底，叶子最小深度先定(都是 1)，再一层层往上回传，单孩子节点只走有孩子那侧。
3. 5visiting 7 → 先递归左右子树深度优先往下走，现在踩到节点 7，它左右孩子都在。后序遍历先把它挂在递归栈上(绿)，等左右子树都算完，再取较浅的那侧 +1。
4. 6visiting 4 → 先递归左右子树踩到节点 4，它只有左孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。
5. 7visiting 2 → 先递归左右子树深度优先往下走，现在踩到节点 2，它左右孩子都在。后序遍历先把它挂在递归栈上(绿)，等左右子树都算完，再取较浅的那侧 +1。
6. 8visiting 1 → 先递归左右子树走到叶子节点 1。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。
7. 91: 叶子 → 1节点 1 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。
8. 10visiting 3 → 先递归左右子树走到叶子节点 3。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。
9. 113: 叶子 → 1节点 3 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。
10. 122: min(1,1)+1 = 2节点 2 左右子树都回来了：左 1、右 1。两侧都通向叶子，取较浅的那个 +1，得到最小深度 = min(1,1)+1 = 2。算完标蓝(已定)，回传给父节点。
11. 134: 只有左(深度2) → 2+1 = 3节点 4 只有左孩子。右侧是空的，但绝不能拿右侧的 0 来算(那会得到 0+1=1，把它当成叶子)。最小深度只能沿有孩子的左侧走：左子树深度 2，所以它的深度 = 2+1 = 3。
12. 14visiting 9 → 先递归左右子树深度优先往下走，现在踩到节点 9，它左右孩子都在。后序遍历先把它挂在递归栈上(绿)，等左右子树都算完，再取较浅的那侧 +1。
13. 15visiting 6 → 先递归左右子树踩到节点 6，它只有右孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。
14. 16visiting 8 → 先递归左右子树走到叶子节点 8。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。
15. 178: 叶子 → 1节点 8 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。
16. 186: 只有右(深度1) → 1+1 = 2节点 6 只有右孩子。左侧是空的，但不能用左侧的 0(否则算出 1，假装它是叶子，得到偏小的假深度)。最小深度必须沿有孩子的右侧走：右子树深度 1，所以它的深度 = 1+1 = 2。
17. 19visiting 13 → 先递归左右子树踩到节点 13，它只有右孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。
18. 20visiting 15 → 先递归左右子树踩到节点 15，它只有右孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。
19. 21visiting 20 → 先递归左右子树走到叶子节点 20。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。
20. 2220: 叶子 → 1节点 20 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。
21. 2315: 只有右(深度1) → 1+1 = 2节点 15 只有右孩子。左侧是空的，但不能用左侧的 0(否则算出 1，假装它是叶子，得到偏小的假深度)。最小深度必须沿有孩子的右侧走：右子树深度 1，所以它的深度 = 1+1 = 2。
22. 2413: 只有右(深度2) → 2+1 = 3节点 13 只有右孩子。左侧是空的，但不能用左侧的 0(否则算出 1，假装它是叶子，得到偏小的假深度)。最小深度必须沿有孩子的右侧走：右子树深度 2，所以它的深度 = 2+1 = 3。
23. 259: min(2,3)+1 = 3节点 9 左右子树都回来了：左 2、右 3。两侧都通向叶子，取较浅的那个 +1，得到最小深度 = min(2,3)+1 = 3。算完标蓝(已定)，回传给父节点。
24. 267: min(3,3)+1 = 4节点 7 左右子树都回来了：左 3、右 3。两侧都通向叶子，取较浅的那个 +1，得到最小深度 = min(3,3)+1 = 4。算完标蓝(已定)，回传给父节点。
25. 27root.minDepth = min(3,3)+1 = 4回到根节点 7：左子树深度 3、右子树深度 3，取较浅的 +1 = 4。最短的一条路是 7→9→6→8 这 4 层 —— 它之所以是答案，正是因为单孩子节点 6 老老实实走了有孩子的那一侧，没有偷偷把空侧当叶子。

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;             // 空节点：深度 0（出口）
        if (root.left == null && root.right == null)
            return 1;                           // 叶子：深度 1
        if (root.left == null)                  // 只有右孩子：必须走右
            return minDepth(root.right) + 1;
        if (root.right == null)                 // 只有左孩子：必须走左
            return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left),    // 两个孩子：取较浅 + 1
                        minDepth(root.right)) + 1;
    }
}

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if root is None:                        # 空节点：深度 0
            return 0
        if root.left is None and root.right is None:
            return 1                            # 叶子：深度 1
        if root.left is None:                   # 只有右孩子：必须走右
            return self.minDepth(root.right) + 1
        if root.right is None:                  # 只有左孩子：必须走左
            return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left),    # 两个孩子：取较浅 + 1
                   self.minDepth(root.right)) + 1

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;          // 空节点：深度 0
        if (!root->left && !root->right)
            return 1;                           // 叶子：深度 1
        if (!root->left)                        // 只有右孩子：必须走右
            return minDepth(root->right) + 1;
        if (!root->right)                       // 只有左孩子：必须走左
            return minDepth(root->left) + 1;
        return min(minDepth(root->left),        // 两个孩子：取较浅 + 1
                   minDepth(root->right)) + 1;
    }
};

复杂度

面试官可能追问