0404. Sum of Left Leaves¶
题目信息¶
- 题号:
0404
- 难度:
Easy
- 主题:
二叉树、左孩子、叶节点、节点值求和
- 原题:
- 重点:
节点必须同时是父节点的左孩子和叶节点、根节点不算左叶、返回所有左叶值之和
题目重述¶
给定二叉树根节点 root,返回树中所有左叶节点的节点值之和。左叶节点必须由其父节点的左指针指向,并且自身的左、右子节点都为空。
根节点没有父节点,因此即使整棵树只有根节点,它也不是左叶节点。某个节点是左孩子但仍有子节点时,也不能计入结果。树中节点数位于 [1, 1000],节点值位于 [-1000, 1000]。
自建示例¶
左右子树都含左叶:
输入:root = [6, 2, 9, -3, 4, 8, null]
输出:5
解释:节点 -3 是节点 2 的左叶,节点 8 是节点 9 的左叶;总和为 -3 + 8 = 5。
只有根节点:
输入:root = [12]
输出:0
解释:根节点没有父节点,不能被视为左叶节点。
在递归参数中保留“是否为左孩子”¶
叶节点本身只说明它没有孩子,还需要知道它是否由父节点的左指针指向。因此递归同时传递 isLeft:到达空节点贡献 0,到达叶节点时只有 isLeft 为真才把节点值加入;非叶节点继续访问左右子树并分别传入 true、false。根节点传入 false,自动排除根被误算为左叶。
C++ 实现¶
class Solution {
int sum(TreeNode* node, bool isLeft) {
if (node == nullptr) return 0;
if (node->left == nullptr && node->right == nullptr) {
return isLeft ? node->val : 0;
}
return sum(node->left, true)
+ sum(node->right, false);
}
public:
int sumOfLeftLeaves(TreeNode* root) {
return sum(root, false);
}
};
代码分析¶
“左孩子”和“叶节点”两个条件在同一个递归状态中同时判断,左孩子但仍有子树的节点不会提前计入。每个节点访问一次,时间复杂度为 O(n),递归栈空间为 O(h)。