Easy

题目描述

给定二叉树的根节点 root，返回所有左叶子之和。

叶子是指没有子节点的节点。左叶子是指作为另一个节点左子节点的叶子节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：24
解释：在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2：

输入：root = [1]
输出：0

约束条件：

  • 节点数在 [1, 1000] 范围内
  • -1000 <= Node.val <= 1000

解题思路

这道题的关键是如何判断一个节点是否为左叶子。我们需要明确左叶子的定义：既是叶子节点，又是父节点的左子节点。

解题思路有两种常见方法：

方法一：递归 DFS（推荐）

  • 从根节点开始遍历，对于每个节点，检查其左子节点是否为叶子
  • 如果左子节点是叶子，将其值加入结果
  • 然后递归处理左右子树
  • 这种方法思路清晰，代码简洁

方法二：迭代 BFS/DFS

  • 使用栈或队列进行层序或前序遍历
  • 在遍历过程中识别左叶子节点并累加

核心难点在于如何准确识别左叶子：

  1. 当前节点有左子节点
  2. 左子节点没有任何子节点（是叶子）
  3. 满足以上条件时，左子节点就是左叶子

需要注意的边界情况：

  • 根节点本身是叶子时，它不是左叶子（因为没有父节点）
  • 只有右子节点的情况

代码实现

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        
        int sum = 0;
        // 检查左子节点是否为左叶子
        if (root->left && !root->left->left && !root->left->right) {
            sum += root->left->val;
        }
        
        // 递归处理左右子树
        sum += sumOfLeftLeaves(root->left);
        sum += sumOfLeftLeaves(root->right);
        
        return sum;
    }
};

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        sum_val = 0
        # 检查左子节点是否为左叶子
        if root.left and not root.left.left and not root.left.right:
            sum_val += root.left.val
        
        # 递归处理左右子树
        sum_val += self.sumOfLeftLeaves(root.left)
        sum_val += self.sumOfLeftLeaves(root.right)
        
        return sum_val

public class Solution {
    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;
        }
        
        // 递归处理左右子树
        sum += SumOfLeftLeaves(root.left);
        sum += SumOfLeftLeaves(root.right);
        
        return sum;
    }
}

var sumOfLeftLeaves = function(root) {
    if (!root) return 0;
    
    let sum = 0;
    // 检查左子节点是否为左叶子
    if (root.left && !root.left.left && !root.left.right) {
        sum += root.left.val;
    }
    
    // 递归处理左右子树
    sum += sumOfLeftLeaves(root.left);
    sum += sumOfLeftLeaves(root.right);
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度递归解法
时间复杂度O(n)
空间复杂度O(h)

其中 n 是二叉树中节点的个数，h 是二叉树的高度。在最坏情况下（完全不平衡的树），空间复杂度为 O(n)；在最好情况下（完全平衡的树），空间复杂度为 O(log n)。