江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第404题：左叶子之和

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

📖 文章摘要

本文详细解析LeetCode第404题“左叶子之和”，这是一道关于二叉树遍历的简单题目。文章提供了完整的解题思路，包含C#、Python、C++三种语言实现，配有详细的图解和性能分析。适合想要学习二叉树遍历的初学者。

核心知识点： 二叉树、深度优先搜索、左叶子节点判断
难度等级： 简单
推荐人群： 初学者，对二叉树遍历感兴趣的读者

题目描述

给定二叉树的根节点 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）来解决。核心思路是：

  1. 判断左叶子节点：

    • 节点是其父节点的左子节点
    • 节点本身是叶子节点（没有左右子节点）

  2. 遍历策略：

    • 使用递归或迭代方式遍历二叉树
    • 对每个节点，检查其左子节点是否为左叶子
    • 累加所有左叶子节点的值

  3. 递归实现：

    • 基本情况：空节点返回0
    • 递归调用左右子树
    • 判断并累加左叶子值

图解思路

二叉树节点分析表

节点值 是否左子节点 是否叶子节点 是否计入和 说明
3 否 否 否 根节点
9 是 是 是 左叶子
20 否 否 否 右子树根节点
15 是 是 是 左叶子
7 否 是 否 右叶子

遍历过程分析表

当前节点 左子节点 右子节点 累加值 说明
3 9 20 0 开始遍历
9 null null 9 找到左叶子
20 15 7 9 继续遍历
15 null null 24 找到左叶子
7 null null 24 右叶子不计入

代码实现

C# 实现

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;
    }
}

Python 实现

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        def is_leaf(node):
            return node and not node.left and not node.right
        
        sum_val = 0
        
        # 使用栈进行迭代遍历
        stack = [(root, False)]  # (node, is_left)
        while stack:
            node, is_left = stack.pop()
            
            # 如果是左叶子节点，累加其值
            if is_left and is_leaf(node):
                sum_val += node.val
            
            # 将右子节点压入栈
            if node.right:
                stack.append((node.right, False))
            # 将左子节点压入栈
            if node.left:
                stack.append((node.left, True))
        
        return sum_val

C++ 实现

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (!root) return 0;
        
        int sum = 0;
        
        // 使用队列进行层序遍历
        queue<pair<TreeNode*, bool>> q;  // {node, is_left}
        q.push({root, false});
        
        while (!q.empty()) {
            auto [node, is_left] = q.front();
            q.pop();
            
            // 检查是否为左叶子
            if (is_left && !node->left && !node->right) {
                sum += node->val;
            }
            
            // 将左右子节点加入队列
            if (node->left) {
                q.push({node->left, true});
            }
            if (node->right) {
                q.push({node->right, false});
            }
        }
        
        return sum;
    }
};

执行结果

C# 实现

  • 执行用时：88 ms
  • 内存消耗：38.4 MB

Python 实现

  • 执行用时：32 ms
  • 内存消耗：15.7 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：13.2 MB

性能对比

语言 执行用时 内存消耗 特点
C# 88 ms 38.4 MB 递归实现简洁
Python 32 ms 15.7 MB 迭代实现灵活
C++ 4 ms 13.2 MB 层序遍历高效

代码亮点

  1. 🎯 三种不同的遍历方式实现
  2. 💡 清晰的左叶子判断逻辑
  3. 🔍 完整的空节点处理
  4. 🎨 代码结构优雅，易于理解

常见错误分析

  1. 🚫 忽略空节点的处理
  2. 🚫 错误判断左叶子节点
  3. 🚫 重复计算叶子节点
  4. 🚫 遍历方式选择不当

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
递归DFS O(n) O(h) 代码简洁 栈空间消耗
迭代DFS O(n) O(n) 控制灵活 代码较长
层序BFS O(n) O(w) 直观清晰 队列开销

相关题目

📖 系列导航

🔥 LeetCode 二叉树专题 - 查看更多精选题解

📢 关注更新：题解持续更新中，欢迎关注获取最新动态！

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！