二叉树的最小深度

这就是最小深度和最大深度最大的不同。最大深度里空侧取 0 无所谓(反正要 max)；但最小深度求的是到最近叶子，空子树根本没有叶子，不能把它当成「0 步可达的叶子」。所以单孩子节点必须绕开空侧、走有孩子那边。下面逐节点看。

准备 · 整棵树：先看清这棵树：根是 7。树里有几个只有一个孩子的节点，它们不是叶子。接下来从根出发做后序 DFS——扎到底，叶子最小深度先定(都是 1)，再一层层往上回传，单孩子节点只走有孩子那侧。

访问节点 7：深度优先往下走，现在踩到节点 7，它左右孩子都在。后序遍历先把它挂在递归栈上(绿)，等左右子树都算完，再取较浅的那侧 +1。

访问节点 4 · 单孩子：踩到节点 4，它只有左孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。

访问节点 2：深度优先往下走，现在踩到节点 2，它左右孩子都在。后序遍历先把它挂在递归栈上(绿)，等左右子树都算完，再取较浅的那侧 +1。

访问节点 1 · 叶子：走到叶子节点 1。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。

回传 1 · 最小深度 = 1：节点 1 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。

访问节点 3 · 叶子：走到叶子节点 3。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。

回传 3 · 最小深度 = 1：节点 3 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。

回传 2 · 最小深度 = 2：节点 2 左右子树都回来了：左 1、右 1。两侧都通向叶子，取较浅的那个 +1，得到最小深度 = min(1,1)+1 = 2。算完标蓝(已定)，回传给父节点。

回传 4 · 最小深度 = 3：节点 4 只有左孩子。右侧是空的，但绝不能拿右侧的 0 来算(那会得到 0+1=1，把它当成叶子)。最小深度只能沿有孩子的左侧走：左子树深度 2，所以它的深度 = 2+1 = 3。

访问节点 9：深度优先往下走，现在踩到节点 9，它左右孩子都在。后序遍历先把它挂在递归栈上(绿)，等左右子树都算完，再取较浅的那侧 +1。

访问节点 6 · 单孩子：踩到节点 6，它只有右孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。

访问节点 8 · 叶子：走到叶子节点 8。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。

回传 8 · 最小深度 = 1：节点 8 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。

回传 6 · 最小深度 = 2：节点 6 只有右孩子。左侧是空的，但不能用左侧的 0(否则算出 1，假装它是叶子，得到偏小的假深度)。最小深度必须沿有孩子的右侧走：右子树深度 1，所以它的深度 = 1+1 = 2。

访问节点 13 · 单孩子：踩到节点 13，它只有右孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。

访问节点 15 · 单孩子：踩到节点 15，它只有右孩子，是个单孩子节点 —— 这正是本题最容易翻车的地方。它不是叶子，不能在这里收尾；缺的那侧是空，但空不代表「0 步就到叶子」，所以必须钻进有孩子的那一边继续找叶子。

访问节点 20 · 叶子：走到叶子节点 20。它没有任何孩子，是一条路径的真正终点，所以它的最小深度 = 1。最小深度求的是「到最近叶子的距离」，而叶子必须是左右孩子都为空的节点。

回传 20 · 最小深度 = 1：节点 20 是叶子，最小深度直接定为 1。它先把这个 1 回传给父节点。

回传 15 · 最小深度 = 2：节点 15 只有右孩子。左侧是空的，但不能用左侧的 0(否则算出 1，假装它是叶子，得到偏小的假深度)。最小深度必须沿有孩子的右侧走：右子树深度 1，所以它的深度 = 1+1 = 2。

回传 13 · 最小深度 = 3：节点 13 只有右孩子。左侧是空的，但不能用左侧的 0(否则算出 1，假装它是叶子，得到偏小的假深度)。最小深度必须沿有孩子的右侧走：右子树深度 2，所以它的深度 = 2+1 = 3。

回传 9 · 最小深度 = 3：节点 9 左右子树都回来了：左 2、右 3。两侧都通向叶子，取较浅的那个 +1，得到最小深度 = min(2,3)+1 = 3。算完标蓝(已定)，回传给父节点。

回传 7 · 最小深度 = 4：节点 7 左右子树都回来了：左 3、右 3。两侧都通向叶子，取较浅的那个 +1，得到最小深度 = min(3,3)+1 = 4。算完标蓝(已定)，回传给父节点。

答案 · 最小深度 = 4：回到根节点 7：左子树深度 3、右子树深度 3，取较浅的 +1 = 4。最短的一条路是 7→9→6→8 这 4 层 —— 它之所以是答案，正是因为单孩子节点 6 老老实实走了有孩子的那一侧，没有偷偷把空侧当叶子。