二叉树的所有路径

笨办法也是好办法:顺着树一杆子捅到底(深度优先)。每进一个节点,路径末尾就多一个它;一旦发现是叶子,这条路就完整了,存下来;然后退回岔路口换条路再扎。

先把这棵树看清楚：绿色的 4、5、6 是叶子(下面再没有孩子)。我们的目标:找出根 1 到每个叶子的完整走法,一共会有三条路。

标出谁是中间节点、谁是叶子：蓝色的 1、2、3 是中间节点(还有孩子),路过但不收;绿色的 4、5、6 才是叶子,是路径的终点。心里先有这张图,走起来就清楚了。

所以输出顺序是先把 2 这边两条走完("1->2->4"、"1->2->5"),再走 3 这边("1->3->6")。理解这个「一头扎到底、再回头」的顺序,后面看每一帧就不会乱。

DFS 第 1 步 · 进根 1：从根 1 出发,当前路径就是 "1"。1 有孩子,不是叶子,继续往下探它的左孩子。

下探 · 进 1 的左孩子 2：进入 2,把它接到路径后面 → "1->2"。1 已经在路径里(变成路径节点)。2 还有孩子,继续往下探它的左孩子。

下探 · 进 2 的左孩子 4：进入 4,路径变成 "1->2->4"。先别急着收——得问一句:4 是叶子吗?

判定 · 4 是叶子吗?：4 左右都没孩子 → 是叶子,这条 "1->2->4" 走到头了,可以收。

收第 1 条路径：把 "1->2->4" 存进结果列表。这条分支探完了,接下来要往回退到 2,去看它还没走过的另一个孩子。

回溯 · 从 4 退回 2：从 4 退回 2:路径里的 4 被撤销,回到 "1->2"。4 这格标记成已探完(变灰)。2 还有个右孩子 5 没走,去探它。

下探 · 进 2 的右孩子 5：进入 5,路径变成 "1->2->5"。同样先判一句:5 是叶子吗?

判定 · 5 是叶子吗?：5 左右都没孩子 → 是叶子,"1->2->5" 走到头,收下第二条。

收第 2 条路径：把 "1->2->5" 也存进结果。5 探完,2 的左右孩子都走过了——该退回 2,再退回根 1 了。

回溯 · 从 5 退回 2：从 5 退回 2:5 被撤销并标记已探完,回到 "1->2"。2 的两个孩子(4、5)现在全是灰的——2 这棵子树彻底探完。

回溯 · 从 2 退回根 1：继续退,从 2 退回 1,路径里的 2 也撤销,回到 "1"。整棵左子树(2 那一片)已探完(全灰)。

根 1 的左孩子探完 · 换右孩子：1 的左孩子 2 整片探完了。DFS 的规矩:左边走干净了才回头走右边。现在轮到 1 的右孩子 3。

下探 · 进 1 的右孩子 3：进入 1 的右孩子 3,路径变成 "1->3"。3 还有个右孩子 6,不是叶子,继续往下探。

下探 · 进 3 的右孩子 6：进入 6,路径变成 "1->3->6"。3 的左孩子是空,只有右孩子 6 这条路。

判定 · 6 是叶子吗?：6 左右都没孩子 → 是叶子,"1->3->6" 也走到头了,第三条路收下。

收第 3 条路径：把 "1->3->6" 存进结果。6 探完,退回 3、再退回 1——此时 1 的左右孩子都走过了,整棵树遍历结束。

全部完成：三条路径全找到:"1->2->4"、"1->2->5"、"1->3->6"。DFS + 回溯就是这样:深入到叶子收一条,退回换条路再深入,直到走遍所有分支。

为什么走 3 的时候路径不是 "1->2->5->3"?因为退回 1 时,2、4、5 已经被撤销了。「进来加、出去撤」让每条分支看到的都是干净的前缀。

本题用「按值传参」让撤销自动发生;若改成共享一个 list,就得手动 path.pop() 来撤销。两种写法本质都是这三步。认准它,全排列/子集/组合一类题全打通。

雷区实演 · 把中间节点也收了：如果忘了判叶子,走到 1 收一条 "1"、走到 2 又收一条 "1->2"……半截路径全冒出来了。必须确认「左右孩子都为空」才是真正的路径终点。

边界三连：单节点要特别注意:根同时也是叶子,路径就是 "1" 一个字符,不带任何箭头。

面试追问：递归出口、迭代写法、手动回溯,是这题面试常被追的三点。