028 · Sum of Left Leaves

algorithm

Published

June 3, 2026

My First Thoughts

这道题的核心是找到“左叶子”。先把这个词拆开看，会清楚很多。

叶子节点比较好判断：一个节点没有左孩子，也没有右孩子，它就是叶子节点：

node.left is None and node.right is None

但“左”这一半更别扭一点。一个节点自己并不知道“我是左孩子还是右孩子”，这个身份来自它的父节点。一般来说，如果 node1.left = node2，那么 node2 才是 node1 的左孩子。所以判断一个节点是不是左叶子，最好从它的父节点出发。

先写一个判断叶子的 helper：

def leaf(node):
    if node.left is None and node.right is None:
        return True
    return False

接下来就可以围绕某个节点 node 去推：

如果 node is None，说明这里没有节点，直接返回 0 就行。

如果 node.left is None，左边没有东西，那左分支肯定贡献不了左叶子，只需要继续递归右分支。

如果 node.right is None，那就继续递归左分支。

然后最关键的是这一句：如果 node.left 是叶子，那么它就是一个左叶子，可以把它的值加进答案：

if leaf(node.left):
    Sum += node.left.val
else:
    Sum += leftsum(node.right) + leftsum(node.left)

return Sum

这个方向上最重要的观察是对的：左叶子要由它的父节点发现。也就是说，不是站在当前节点这里问“我是不是左叶子”，而是站在父节点这里问“我的左孩子是不是叶子”。

Why That Is Not Enough

上面的思路已经接近答案了，真正需要整理的是递归分支的顺序。

最容易出问题的是这类提前返回：

if node.right is None:
    return leftsum(node.left)

看一个很小的例子：

  1
 /
2

节点 2 是节点 1 的左孩子，而且它没有左右孩子，所以 2 是左叶子，答案应该是 2。

但如果在节点 1 这里看到 node.right is None 就直接递归到 leftsum(node.left)，接下来函数会站在节点 2 的位置继续判断。到了节点 2 时，它自己只是一个叶子，但它已经看不到“我是父节点的左孩子”这件事了。如果递归函数只从当前节点出发，就很容易把这个值漏掉。

所以这道题的判断顺序应该更稳定一点：每到一个节点，先检查它的左孩子是不是叶子。如果是，立刻把左孩子的值加进去；如果不是，再继续递归左子树。右子树也要递归，因为右子树里面仍然可能有别的左叶子。

另外，leaf(node) 还需要能处理 None。因为有些节点没有左孩子，我们可能会检查 leaf(node.left)，这时 node.left 是 None。如果 helper 里面直接访问 node.left，会出错。让 None 直接返回 False，后面的代码会简单很多。

Final Idea

关键思路可以压成一句话：

每个节点负责检查自己的左孩子；如果左孩子是叶子，就把左孩子的值加入答案。

先把叶子判断写稳：

def is_leaf(node):
    return node is not None and node.left is None and node.right is None

这个 helper 的含义很单纯：node 存在，并且没有左右孩子，才是叶子。None 不是叶子。

然后定义递归函数：

sumOfLeftLeaves(root) 返回以 root 为根的这棵子树中，所有左叶子节点的值之和。

如果 root is None，空树里没有左叶子，返回 0。

接下来站在 root 这里看它的左孩子：

if is_leaf(root.left):
    total += root.left.val

如果 root.left 是叶子，那么它就是一个左叶子，直接加上它的值。

如果 root.left 不是叶子，就说明左边要么是空的，要么是一棵还没走完的子树。空树递归返回 0，非空子树继续找里面的左叶子：

else:
    total += sumOfLeftLeaves(root.left)

最后右子树也不能漏。虽然 root.right 本身不是 root 的左孩子，但它的内部仍然可能有左叶子。比如示例里的 15，它在整棵树上位于右子树里，但它是节点 20 的左孩子，所以仍然要算：

total += sumOfLeftLeaves(root.right)

把这些合起来，就是完整解法。

Why It Works

递归函数 sumOfLeftLeaves(root) 的含义是：返回以 root 为根的子树里所有左叶子的值之和。

空节点没有任何子树，也没有左叶子，所以返回 0。

对于一个非空节点 root，所有答案只可能来自两类地方。第一类是 root.left 自己：如果它是叶子，那么它正好是一个左叶子，应该把 root.left.val 加进来。第二类是左右子树内部更深处的左叶子，这些可以交给递归继续统计。

这里不会漏掉右子树，是因为“左叶子”说的是某个节点相对于它自己的父节点是左孩子，而不是必须出现在整棵树的左边。右子树里面的节点也可能是它父节点的左孩子。

每个左叶子都会在它的父节点那里被发现一次；不是左叶子的节点不会通过 is_leaf(root.left) 这个检查。因此最后得到的和正好包含所有左叶子，一项不多，一项不少。

Code

def sumOfLeftLeaves(root):
    def is_leaf(node):
        return node is not None and node.left is None and node.right is None

    if root is None:
        return 0

    total = 0

    if is_leaf(root.left):
        total += root.left.val
    else:
        total += sumOfLeftLeaves(root.left)

    total += sumOfLeftLeaves(root.right)

    return total

Complexity

Time	\(O(n)\) - 每个节点最多被访问一次
Space	\(O(h)\) - 递归调用栈的深度等于树的高度 `h`，最坏情况下可以到 \(O(n)\)

Takeaway

有些二叉树题不能只看“当前节点是什么”，还要看“当前节点和父节点是什么关系”。这道题里，“是不是叶子”可以由节点自己判断，但“是不是左孩子”要由父节点判断。递归时先说清楚函数返回的是“一棵子树里的左叶子之和”，再让每个父节点负责检查自己的左孩子，逻辑就会顺很多。

← Quiz