求根节点到叶节点数字之和

拼十进制就是「进位」:已有 49,再来个 5,就是 49×10+5 = 495。所以 DFS 时带着一个 cur 往下传,每进一个节点就更新它,到叶子时 cur 正好是这条路径的完整数字。

先把这棵树看清楚：绿色的 5、1、0 是叶子(下面再没有孩子)。我们要找的:根 4 到每个叶子的路径,把路上数字拼成整数,再求和。一共三条路。

标出中间节点和叶子：蓝色的 4、9 是中间节点(还有孩子),只更新 cur、不结算;绿色的 5、1、0 才是叶子,走到才把这条路径拼成的数加进总和。

顺序是先走 4→9 这一片(把 495、491 两条结算掉),再走 4→0(结算 40)。cur 用「按值传参」往下带,退回上层时自动变回上层的值,不用手动撤销。

DFS 第 1 步 · 进根 4：从根 4 出发,cur 从 0 更新成 0×10+4 = 4。4 有孩子,不是叶子,带着 cur=4 继续往下探它的左孩子。

下探 · 进 4 的左孩子 9：进入 9,cur 更新成 4×10+9 = 49。4 已经在路径上(变成路径节点)。9 还有孩子,带着 cur=49 继续探它的左孩子。

判定 · 9 是叶子吗?：9 有孩子(5 和 1),不是叶子,所以现在不结算、cur 也不动,带着 cur=49 先往下探它的左孩子 5。

下探 · 进 9 的左孩子 5：进入 5,cur 更新成 49×10+5 = 495。先别急——得问一句:5 是叶子吗?

判定 · 5 是叶子吗?：5 左右都没孩子 → 是叶子,这条路径 4→9→5 拼出的数 495 走到头了,该加进总和。

结算第 1 条 · 总和 += 495：把 495 加进总和,总和从 0 变成 495。这条分支探完了,接下来要往回退到 9,去看它还没走的另一个孩子。

回溯 · 从 5 退回 9：从 5 退回 9:cur 自动恢复成上层的 49(按值传参的好处)。5 这格标记成已探完(变灰)。9 还有个右孩子 1 没走,带着 cur=49 去探它。

下探 · 进 9 的右孩子 1：进入 1,cur 更新成 49×10+1 = 491。注意 cur 是从恢复后的 49 算的,不会带上刚才 5 那条的痕迹。同样先判:1 是叶子吗?

判定 · 1 是叶子吗?：1 左右都没孩子 → 是叶子,路径 4→9→1 拼出 491,走到头,结算第二条。

结算第 2 条 · 总和 += 491：把 491 加进总和,总和从 495 变成 986。1 探完,9 的左右孩子都走过了——该退回 9,再退回根 4 了。

回溯 · 从 1 退回 9 再退回 4：1 探完退回 9,9 的两个孩子全灰了(整片探完),再从 9 退回根 4,cur 一路恢复成 4。整棵左子树(9 那一片)已探完(全灰)。

根 4 的左孩子探完 · 换右孩子：4 的左孩子 9 整片探完了。DFS 的规矩:左边走干净了才回头走右边。现在 cur=4,轮到 4 的右孩子 0。

判定 · 4 是叶子吗?：根 4 本身有孩子,不是叶子,所以 4 自己从不被结算——它的结果是「左子树之和 + 右子树之和」。左边 986 已到手,带着 cur=4 去探右孩子 0。

下探 · 进 4 的右孩子 0：进入 0,cur 更新成 4×10+0 = 40。判一句:0 是叶子吗?

判定 · 0 是叶子吗?：0 左右都没孩子 → 是叶子,路径 4→0 拼出 40,第三条也走到头了。

结算第 3 条 · 总和 += 40：把 40 加进总和,总和变成 1026。0 探完,退回 4——此时 4 的左右孩子都走过了,整棵树遍历结束。

全部完成：三条路径数字 495、491、40 全部加完,答案 1026。核心就一句:DFS 沿路 cur=cur*10+val,到叶子把 cur 加进总和。

走完 5 退回 9 时,cur 自动是 49 而不是 495——因为传进 5 的那个 495 是「副本」,9 这层手里的 cur 一直是 49。这就是「按值传参」省掉手动回溯的原理。

本题携带的是「拼出的数字」;LC112/113 携带的是「路径和」;LC1448 携带的是「路上最大值」。换汤不换药——DFS 沿路带个累积量,到叶子做判定/结算,这一套能打通一大片树形题。

雷区实演 · 把中间节点也结算了：如果忘了判叶子,走到 4 就加个 4、走到 9 又加个 49……半截数全混进总和。必须确认「左右孩子都为空」才结算,只有叶子手里的 cur 才是一条完整路径数。

边界三连：单节点要注意:根同时也是叶子,cur=0×10+5=5,直接返回 5。斜树没有分叉,就一条路一直拼到底。

面试追问：递归出口、迭代写法、溢出处理,是这题面试常被追的三点。