What defines a left leaf in this problem?

A left leaf is a node with no children that is the left child of its parent.

Can I use BFS instead of DFS for Sum of Left Leaves?

Yes, BFS works as long as you track whether each node is a left child and check for leaf nodes before adding to the sum.

How do I handle a tree with only the root node?

The root is not a left child, so the sum of left leaves is 0 in this case.

What is the time and space complexity of the standard approach?

Time complexity is O(n) because every node is visited once; space is O(h) for DFS recursion or O(n) for BFS queue, with h as tree height.

Does this problem require tracking parent nodes?

Not explicitly; you only need to know if a node is a left child while traversing to correctly identify left leaves.

#404

Easy

auto_awesome二分·树·traversal

LeetCode 题解工作台

左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。示例 1：输入: root = [3,9,20,null,null,15,7] 输出: 24 解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24 示例 2: 输入: root = [1] 输出: 0 提示: 节点数在 […

树深度优先搜索广度优先搜索二叉树

题目描述

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

提示:

节点数在 [1, 1000] 范围内
-1000 <= Node.val <= 1000

lightbulb

解题思路

方法一：递归

我们首先判断 root 是否为空，如果为空则返回 $0$ 。

否则，我们递归调用 sumOfLeftLeaves 函数计算 root 的右子树中所有左叶子之和，并将结果赋给答案变量 $ans$ 。然后我们判断 root 的左子节点是否存在，如果存在，我们判断其是否为叶子节点，如果是叶子节点，则将其值加到答案变量 $ans$ 中，否则我们递归调用 sumOfLeftLeaves 函数计算 root 的左子树中所有左叶子之和，并将结果加到答案变量 $ans$ 中。

最后返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉树的节点个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        ans = self.sumOfLeftLeaves(root.right)
        if root.left:
            if root.left.left == root.left.right:
                ans += root.left.val
            else:
                ans += self.sumOfLeftLeaves(root.left)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each node is visited once, and space complexity is O(h) for recursion stack in DFS or O(n) for BFS queue, where h is tree height and n is number of nodes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask for traversal strategy before coding.
question_mark
Probe how to identify left leaves without extra storage.
question_mark
Expect handling of edge cases like single-node or all-right-child trees.

warning

常见陷阱

外企场景

error
Confusing left children with left leaves and summing non-leaf nodes.
error
Forgetting to check for null nodes in recursive or iterative traversal.
error
Mixing DFS and BFS state tracking, causing incorrect sums in deeper subtrees.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sum of right leaves instead of left leaves using similar traversal.
arrow_right_alt
Compute sum of leaves at odd tree levels only, requiring level tracking.
arrow_right_alt
Sum all leaves without distinguishing left or right child, simplifying state management.

help

常见问题

外企场景

继续练习

#449 序列化和反序列化二叉搜索树 #297 二叉树的序列化与反序列化 #513 找树左下角的值