LeetCode 404. 左叶子之和
题目描述
题意分析
求所有左叶子的值之和。一个节点必须同时满足两个条件：它是父节点的左孩子，并且自己的左右孩子都为空。
“左”只看它与直接父节点的关系，与它位于整棵树的哪一侧无关。根节点没有父节点，即使根本身是叶子，也不能计入答案。
解法：DFS 记录是否来自左边
核心思路
[!blue]
节点本身的左右指针可以判断它是不是叶子，却不能说明它是不是父节点的左孩子。因此递归时多带一个
isLeft，表示当前节点是否从父节点的左指针进入。
dfs(node, isLeft)返回当前子树中的左叶子之和。空节点没有贡献，返回零；当前节点是叶子时，只有isLeft为真才返回它的值，否则返回零。当前节点不是叶子时，它自身不能计入，答案完全来自左右子树。分别递归左孩子并传
true、右孩子并传false，再把两个结果相加。两棵子树互不重叠，所有叶子都会恰好被判断一次。
解题步骤
- 从
dfs(root, false)开始，明确根节点不属于左孩子。- 遇到空节点返回零，避免访问空指针。
- 若两个孩子都为空，根据
isLeft返回节点值或零，结束当前递归。- 否则分别计算
dfs(node.left, true)和dfs(node.right, false)，返回两者之和。方向标记每次重新设置，不沿用父节点的标记。
代码实现
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)$，递归栈深度等于树高；树退化成链时为 $O(n)$。
关键点总结
[!green]
- 左孩子与左叶子不同，必须同时检查两个孩子为空。
- 方向标记每条边重新确定。
易错点总结
[!yellow]
- 把所有左孩子计入，会错误加入非叶节点。
- 将父方向传给右孩子，会把右叶子误判为左叶子。
- 单节点树的根不能计入答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 872. 叶子相似的树 | 简单 | 同样识别没有孩子的叶子，本题还要求它是父节点的左孩子，原题收集全部叶值。 |
| 257. 二叉树的所有路径 | 简单 | 同样在叶子处收集信息，本题只累加符合左右身份的叶值，原题保存整条根路径。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！