左叶子之和 图解题解

这道题到底在问什么

树

[3,9,20,null,null,15,7]

输出

24

说明

左叶子是 9 和 15,9 + 15 = 24

先想最直接的笨办法

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

最优解：一步一步想明白

1. 3千万别只看「是不是叶子」。7 是叶子,但它是 20 的右孩子,不算;20 是 3 的右孩子,而且它下面挂着 15、7、不是叶子,更不算。两条都满足才数。
2. 4根=3, 左叶子=9 / 15绿色的 9 和 15 就是要找的左叶子。9 是根 3 的左孩子且没孩子;15 是 20 的左孩子且没孩子。其它节点都不数。
3. 57 是叶子,但是「右」孩子同样挂在 20 下面:15 是左孩子所以数,7 是右孩子所以不数。这就是「左」字的分量,位置不同,结果天差地别。
4. 620 是右孩子,而且不是叶子再看 20:它是根 3 的右孩子、本身又不是叶子(下面挂着 15 和 7),两条全不沾,自然也不数。「左孩子」和「叶子」两条得同时满足。
5. 7笨办法也是好办法:挨个访问每个节点。判断的主语不是「我自己」,而是「我的左孩子」——只要我的左孩子是叶子,那它就是一个左叶子,加上它的值。
6. 8sum = 0,看 3 的左孩子从根 3 出发,答案 sum = 0。规矩是:站在 3 这里,先看一眼它的左孩子 9 是不是叶子。
7. 9目光移到 9把目光移到 3 的左孩子 9。接下来要查两件事:9 有没有左孩子、有没有右孩子——两个都空才是叶子。
8. 109 左右都空 → 是左叶子!3 的左孩子是 9。看 9:它左右都没孩子 → 9 是叶子,而且它是 3 的左孩子 → 它是一个左叶子,该累加了。
9. 11sum = 0 + 9 = 9把 9 标成绿色(已收),sum 从 0 变成 9。第一个左叶子到手。接着 DFS 继续探 3 的左右孩子(标准遍历)。
10. 12递归进入 9虽然 9 已经被数过了,DFS 仍会递归走进 9(代码是统一遍历)。进到 9 后看它的左孩子——是空,没有可数的左叶子,这一支到头了。
11. 139 左右都空,退回 39 没有任何孩子,递归直接返回,退回根 3。9 标灰(已探完)。3 的左边走完了,接下来按 DFS 规矩去探 3 的右孩子 20。
12. 14递归进入 20,看 20 的左孩子进入 20。同样的动作:站在 20 这里,先看它的左孩子 15 是不是叶子。注意 sum 此刻仍是 9,还没加新东西。
13. 15目光移到 15把目光移到 20 的左孩子 15。和刚才查 9 一样,要确认 15 的左右孩子是不是都空。
14. 1615 左右都空 → 是左叶子!20 的左孩子是 15。看 15:左右都空 → 是叶子,又是 20 的左孩子 → 第二个左叶子找到了,该加。
15. 17sum = 9 + 15 = 24把 15 标绿,sum 从 9 变成 24。两个左叶子都数到了。接下来 DFS 继续把 20 的左右孩子也走一遍(确认没漏)。
16. 187 是叶子,但是右孩子 → 不加顺手看 20 的右孩子 7:它确实是叶子,但它是右孩子,不满足「左」这一条,所以不加。sum 保持 24 不动。
17. 1915 是叶子,无可探DFS 还会递归走进 15(统一遍历)。15 没孩子,看它的左孩子是空,无左叶子可加,直接返回。sum 仍是 24。
18. 207 是叶子,无可探再递归走进 7。7 也没孩子,它的左孩子是空,无左叶子可加,返回。注意:7 自己虽是叶子,但「数不数它」是在它父亲 20 那一步判的,这里不重复判。
19. 21退回节点 207 探完返回,退回 20。15、7 都标灰了。20 的左右孩子都走完,它这一支也该收口,继续往上退回根 3。
20. 2220 的子树全走完20 这棵子树(15、7)全探完,标灰退回根 3。此时 3 的左孩子 9、右孩子 20 都走过了,整棵树遍历结束。
21. 23答案 sum = 24遍历完毕,两个左叶子 9、15 累加得 24。整个过程就是:走到每个节点,顺手判一下「我的左孩子是不是叶子」,是就加上它。
22. 24为什么不站在叶子上判?因为叶子不知道自己是父亲的左孩子还是右孩子(它没有指向父亲的指针)。让父亲来判左孩子,信息现成,一句 if 搞定。
23. 28错误: sum = 9 + 15 + 7 = 31如果只判「是不是叶子」、不管左右,就会把 7 也加进去得到 31。7 是右孩子,不是左叶子。漏掉「左」这个条件,答案就错了。

⚠️ 容易写错的地方

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

class Solution:
    def sumOfLeftLeaves(self, root):
        if not root:
            return 0
        s = 0
        left = root.left
        if left and not left.left and not left.right:
            s += left.val          # 左孩子是叶子 → 左叶子,累加
        else:
            s += self.sumOfLeftLeaves(left)   # 否则继续往左探
        s += self.sumOfLeftLeaves(root.right) # 右子树照常探
        return s

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        int s = 0;
        TreeNode* left = root->left;
        if (left && !left->left && !left->right)   // 左孩子是叶子
            s += left->val;                        // 累加左叶子
        else
            s += sumOfLeftLeaves(left);            // 否则继续探左
        s += sumOfLeftLeaves(root->right);         // 探右
        return s;
    }
};

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int s = 0;
        TreeNode left = root.left;
        if (left != null && left.left == null && left.right == null)  // 左孩子是叶子
            s += left.val;                        // 累加左叶子
        else
            s += sumOfLeftLeaves(left);           // 否则继续探左
        s += sumOfLeftLeaves(root.right);         // 探右
        return s;
    }
}

复杂度

面试官可能追问