06、左叶子之和
2025/11/10大约 3 分钟数据结构算法算法基地面试递归二叉树刷题程序厨校招社招
“左叶子”不是左子树里的所有节点,也不是所有左孩子。一个节点需要同时满足:它是父节点的左孩子,而且它自己没有孩子。
问题与目标
LeetCode 404:左叶子之和要求累加所有左叶子的值。
3
/ \
9 20
/ \
15 7
9 和 15 是左叶子,和为 24;7 是右叶子,不计入。节点 20 虽然位于右子树,但它的左叶子 15 仍然需要统计。
在父节点处检查左孩子
只拿到一个普通树节点,通常无法知道它是父节点的左孩子还是右孩子。最直接的做法是在父节点处判断:左孩子存在,且它的左右孩子都为空,就累加左孩子的值。
然后仍然向左右子树继续搜索,保证右子树内部的左叶子也不遗漏。根节点没有父节点,即使整棵树只有一个根,也不属于左叶子。

用例子核对每一步
处理根 3 时发现左孩子 9 是叶子,累加 9。进入右子树 20,发现它的左孩子 15 是叶子,再累加 15。节点 7 没有左孩子,不产生任何贡献,总计 9 + 15 = 24。
C++17 实现
struct TreeNode {
int val = 0;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
};
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (root == nullptr) return 0;
int contribution = 0;
if (root->left != nullptr && root->left->left == nullptr &&
root->left->right == nullptr) {
contribution = root->left->val;
}
return contribution + sumOfLeftLeaves(root->left) +
sumOfLeftLeaves(root->right);
}
};
这里即使继续访问刚计入的左叶子,也不会再次累加:它没有左孩子,不会在自己的调用中产生贡献。也可以携带 is_left 标记递归,让叶子自己判断是否计入;两种方式选一种并保持一致即可。
复杂度与边界
每个节点访问一次,时间 O(n),调用栈空间 O(h),最坏退化树为 O(n)。题目给定的节点值与节点数量范围使总和能够放入 int;通用接口需要按实际数值范围选择累加类型。
空树和单根节点都返回 0;负数左叶子照常相加,不能只统计正值;只有右孩子的链也返回 0。
常见误区
检查“左孩子存在”还不够,必须确认它是叶子;只递归左子树也不对,因为右子树可能包含左叶子。把题目中的方向条件和结构条件拆开检查,比记住某种遍历顺序更重要。
