404. 左叶子之和（Sum of Left Leaves）

频次 ★★ · 难度 🟢 · 高频：全厂

题目

计算二叉树所有左叶子节点值的和。左叶子：是父节点的左子节点，且自身是叶子节点（左右子节点都为空）。

示例：

输入:    3
       /   \
      9    20
          /  \
         15   7
输出: 24（左叶子 9 + 15 = 24）

思路

递归判断”当前节点的左子节点是否是叶子”：遍历每个节点，检查其左子节点——如果左子节点存在且左右都为空，说明它是左叶子，累加其值。然后递归处理左右子树。

关键：不能从叶子节点自身判断（叶子节点不知道自己是左还是右），必须从父节点判断。

代码

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    int sum = 0;
    // 判断当前节点的左子节点是否是左叶子
    if (root.left != null
        && root.left.left == null
        && root.left.right == null) {
        sum += root.left.val;
    }
    // 递归处理左右子树
    return sum + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

复杂度

• 时间：O(n) —— 每个节点访问一次
• 空间：O(height) —— 递归栈深度

边界条件

• 空树：返回 0
• 单节点：0（根节点不算左叶子）
• 根节点的左子节点是叶子：累加该值
• 所有节点都在右子树：0（没有左叶子）

变式

• 右叶子之和：判断条件改为 root.right 且左右为空
• 所有叶子之和：不需要判断左右，直接累加
• 迭代版：用栈/队列遍历，同样在父节点判断左子节点

易错点

• 不能从叶子节点判断——叶子节点 node.left == null && node.right == null 成立，但无法知道自己是左还是右。必须在父节点层面判断 root.left 是否是叶子
• 递归调用时，sumOfLeftLeaves(root.left) 会继续检查左子节点中的左叶子——不需要额外判断
• 不要写成 sumOfLeftLeaves(root.left.left) 之类的——递归已经处理了

面试追问

• 怎么判断一个节点是左叶子？ 两个条件：1) 它是父节点的左子节点；2) 它自己没有子节点。前者需要从父节点视角判断，后者可以直接判断
• 迭代怎么写？ 用栈/队列，每次弹出节点后检查其左子节点是否是叶子，是则累加。注意迭代时也要把左子节点和右子节点入栈/队

关联题

• 同套路：112. 路径总和 —— 递归时在叶子节点做判断的模式
• 进阶：513. 找树左下角的值 —— 同样关注”左”侧，但找的是最底层最左的节点
• 知识点：递归时从父节点视角判断子节点属性的模式见二叉树