LeetCode 404. 左叶子之和
目录
题目描述
题意分析
输入是一棵二叉树的根节点，要求把所有「左叶子」的值加起来返回。
「左叶子」这个词由两个独立条件合成：一是该节点没有左孩子也没有右孩子，二是它挂在某个父节点的左指针上。两个条件缺一不可，而且第二个条件的信息不在节点自身里——只看一个
TreeNode无法判断它是父节点的左孩子还是右孩子。这决定了整题的走向：遍历时必须把「我是从哪个方向下来的」这一信息一路带下去，或者站在父节点的位置上替孩子做判断。
约束里节点数最多 1000，值域含负数，所以答案可能是负的，不能用「大于 0」之类的条件做剪枝。边界上要覆盖：树只有一个根节点时，根不是任何节点的孩子，答案为
0；整棵树没有左叶子时答案也是0；根为空时返回0。
解法：DFS 记录是否来自左边
核心思路
“左叶子”必须同时满足两个条件：节点是父节点的左孩子，并且左右孩子都为空。它不是“左子树中的所有叶子”，因为右子树内部也可能出现左叶子。
当前节点不知道自己来自父节点的哪一侧，因此递归时额外传入
isLeft。约定dfs(node, isLeft)返回node子树内所有左叶子的值之和，isLeft表示node是否是父节点的左孩子。根节点没有父节点，所以入口必须是dfs(root, false)。若当前节点是叶子，只有
isLeft为真时才返回节点值；否则递归左右子树，分别传入true和false。根据递归契约，两边返回值覆盖且只覆盖各自子树中的左叶子，相加就是当前子树的答案。
解题步骤
- 调用
dfs(root, false)；空树会在递归入口返回0。- 当前节点为空时返回
0。- 当前节点是叶子时，根据
isLeft返回node.val或0。- 当前节点不是叶子时，计算
dfs(node.left, true) + dfs(node.right, false)。以
[3,9,20,null,null,15,7]为例：9和15都以左孩子身份到达叶子分支，分别贡献9、15；7是右叶子，贡献0，答案为24。这也说明左叶子可以位于根的右子树中。
代码实现
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return dfs(root, false);
}
private int dfs(TreeNode node, boolean isLeft) {
if (node == null) {
return 0;
}
if (node.left == null && node.right == null) {
return isLeft ? node.val : 0;
}
return dfs(node.left, true) + dfs(node.right, false);
}
}
func sumOfLeftLeaves(root *TreeNode) int {
var dfs func(*TreeNode, bool) int
dfs = func(node *TreeNode, isLeft bool) int {
if node == nil {
return 0
}
if node.Left == nil && node.Right == nil {
if isLeft {
return node.Val
}
return 0
}
return dfs(node.Left, true) + dfs(node.Right, false)
}
return dfs(root, false)
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次。
- 空间复杂度：$O(h)$，
h为树高，来自递归栈；退化链表时为 $O(n)$，平衡树中为 $O(\log n)$。
关键点总结
- 左叶子是“左孩子”与“叶子”两个条件的交集。
- 节点自身没有父指针，方向信息应作为递归参数向下传递。
- 先明确
dfs的参数和返回值契约，再按空节点、叶子、非叶子三类实现。- 根节点即使没有孩子也不是左叶子，初始方向必须传
false。
易错点总结
- 把“左叶子”理解成“左子树中的叶子”，会漏掉右子树内部的左叶子。
- 只判断
isLeft而不判断叶子，会错误累加左侧内部节点。- 叶子条件必须是左右孩子都为空，不能只检查一侧。
- 根入口传
true，会把单节点树的根误算为左叶子。- 递归右孩子时沿用父节点的方向，会把右叶子错误计入。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 112. 路径总和 | 简单 | 沿途累减目标值，在叶子处判定是否命中 |
| 113. 路径总和 II | 中等 | 要输出全部路径，递归中需要回溯维护路径栈 |
| 129. 求根节点到叶节点数字之和 | 中等 | 向下传递的是拼接出的数字而非方向标记 |
| 257. 二叉树的所有路径 | 简单 | 参数是字符串前缀，考察拼接与回溯的时机 |
| 1022. 从根到叶的二进制数之和 | 简单 | 传递的状态是移位累积的二进制值 |
| 872. 叶子相似的树 | 简单 | 只收集叶子序列并比较两棵树，不关心方向 |
| LCR 049. 求根节点到叶节点数字之和 | 中等 | 与 129 同题，可对照递归与迭代两种实现 |
| 剑指 Offer 34. 二叉树中和为某一值的路径 | 中等 | 目标和路径题，重点在剪枝与结果快照的拷贝 |