左叶子之和

千万别只看「是不是叶子」。7 是叶子,但它是 20 的右孩子,不算;20 是 3 的右孩子,而且它下面挂着 15、7、不是叶子,更不算。两条都满足才数。

先把这棵树看清楚：绿色的 9 和 15 就是要找的左叶子。9 是根 3 的左孩子且没孩子;15 是 20 的左孩子且没孩子。其它节点都不数。

对照看:7 为什么不算?：同样挂在 20 下面:15 是左孩子所以数,7 是右孩子所以不数。这就是「左」字的分量,位置不同,结果天差地别。

对照看:20 为什么不算?：再看 20:它是根 3 的右孩子、本身又不是叶子(下面挂着 15 和 7),两条全不沾,自然也不数。「左孩子」和「叶子」两条得同时满足。

笨办法也是好办法:挨个访问每个节点。判断的主语不是「我自己」,而是「我的左孩子」——只要我的左孩子是叶子,那它就是一个左叶子,加上它的值。

DFS 第 1 步 · 进根 3：从根 3 出发,答案 sum = 0。规矩是:站在 3 这里,先看一眼它的左孩子 9 是不是叶子。

看向 · 3 的左孩子 9：把目光移到 3 的左孩子 9。接下来要查两件事:9 有没有左孩子、有没有右孩子——两个都空才是叶子。

判定 · 3 的左孩子 9 是叶子吗?：3 的左孩子是 9。看 9:它左右都没孩子 → 9 是叶子,而且它是 3 的左孩子 → 它是一个左叶子,该累加了。

累加 · sum += 9：把 9 标成绿色(已收),sum 从 0 变成 9。第一个左叶子到手。接着 DFS 继续探 3 的左右孩子(标准遍历)。

下探 · 进 3 的左孩子 9：虽然 9 已经被数过了,DFS 仍会递归走进 9(代码是统一遍历)。进到 9 后看它的左孩子——是空,没有可数的左叶子,这一支到头了。

9 是叶子 · 无可探,回溯：9 没有任何孩子,递归直接返回,退回根 3。9 标灰(已探完)。3 的左边走完了,接下来按 DFS 规矩去探 3 的右孩子 20。

下探 · 进 3 的右孩子 20：进入 20。同样的动作:站在 20 这里,先看它的左孩子 15 是不是叶子。注意 sum 此刻仍是 9,还没加新东西。

看向 · 20 的左孩子 15：把目光移到 20 的左孩子 15。和刚才查 9 一样,要确认 15 的左右孩子是不是都空。

判定 · 20 的左孩子 15 是叶子吗?：20 的左孩子是 15。看 15:左右都空 → 是叶子,又是 20 的左孩子 → 第二个左叶子找到了,该加。

累加 · sum += 15：把 15 标绿,sum 从 9 变成 24。两个左叶子都数到了。接下来 DFS 继续把 20 的左右孩子也走一遍(确认没漏)。

判定 · 20 的右孩子 7 呢?：顺手看 20 的右孩子 7:它确实是叶子,但它是右孩子,不满足「左」这一条,所以不加。sum 保持 24 不动。

下探 · 递归进入 15：DFS 还会递归走进 15(统一遍历)。15 没孩子,看它的左孩子是空,无左叶子可加,直接返回。sum 仍是 24。

下探 · 递归进入 7：再递归走进 7。7 也没孩子,它的左孩子是空,无左叶子可加,返回。注意:7 自己虽是叶子,但「数不数它」是在它父亲 20 那一步判的,这里不重复判。

回溯 · 7 探完,退回 20：7 探完返回,退回 20。15、7 都标灰了。20 的左右孩子都走完,它这一支也该收口,继续往上退回根 3。

回溯 · 20 探完,退回根 3：20 这棵子树(15、7)全探完,标灰退回根 3。此时 3 的左孩子 9、右孩子 20 都走过了,整棵树遍历结束。

全部完成：遍历完毕,两个左叶子 9、15 累加得 24。整个过程就是:走到每个节点,顺手判一下「我的左孩子是不是叶子」,是就加上它。

为什么不站在叶子上判?因为叶子不知道自己是父亲的左孩子还是右孩子(它没有指向父亲的指针)。让父亲来判左孩子,信息现成,一句 if 搞定。

雷区实演 · 错把右叶子 7 也加了：如果只判「是不是叶子」、不管左右,就会把 7 也加进去得到 31。7 是右孩子,不是左叶子。漏掉「左」这个条件,答案就错了。

边界三连：单根 [1] 要特别注意:根虽然是叶子,但它不是任何节点的左孩子,所以答案是 0,不是 1。

面试追问：判定主语、迭代写法、举一反三改右叶子,是这题面试常被追的三点。