【LeetCode刷题日记】 404：左叶子之和——两种解法带你彻底搞懂二叉树左叶子之和：递归与BFS详解

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

大家好，我是代码不加冰，又来到了每日刷题的时间，今天我们刷的是二叉树相关的算法题，让我们一起来看看吧。

摘要：

本文介绍了计算二叉树所有左叶子节点之和的两种方法。通过示例分析，明确了左叶子的定义：必须是父节点的左子节点且自身无子节点。递归法采用后序遍历思路，在父节点判断左孩子是否为叶子节点；BFS法则通过队列层序遍历，在访问父节点时检查左孩子属性。两种方法都能正确累加左叶子值，但实现思路不同：递归简洁但可能栈溢出，BFS稳定但代码稍复杂。文章通过详细步骤和图解展示了两种解法的执行过程，帮助理解核心判断逻辑和避免重复计算的原理。

题目背景：

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

示例 1：

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

示例 2:

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

提示:

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

题目解析：

初次见到这道题，很多人会想当然地认为：左叶子不就是左边的叶子节点吗，直接遍历左子树不就行了

题目中有一个非常重要的细节：左叶子必须通过它的父节点来判断。也就是说，你不能只盯着当前节点问你是不是左叶子，而要问你的父节点我的左边是不是你

本文将带你理解什么是左叶子，以及如何正确地计算左叶子之和。

左叶子的准确定义：

一个节点是“左叶子”，当且仅当：

1. 它是某个节点的左子节点

2. 它本身是一个叶子节点（没有左右孩子）

判断逻辑图解

text

父节点 / \ 左孩子 右孩子 / \ null null

判断条件（站在父节点）：

text

if (父节点.left != null && 父节点.left.left == null && 父节点.left.right == null) { // 父节点的左孩子是左叶子！ }

具体例子：

3 / \ 9 20 / \ null null

站在节点 3：

• 左孩子是 9

• 9 没有左右孩子 ✅

• 所以 9 是左叶子

站在节点 9：

• 左孩子是 null ❌

• 虽然 9 的左右孩子都是 null（它是叶子），但无法判断自己是不是左叶子

我们这里用两种方式来实现：

递归法：

第1段：边界条件

java

if (root == null) { return 0; }

空树没有左叶子，返回 0。

---

第2段：递归左右子树

java

int leftSum = sumOfLeftLeaves(root.left); int rightSum = sumOfLeftLeaves(root.right);

先递归计算左子树和右子树中的左叶子之和。注意：这里的leftSum不是“左叶子之和”，而是“左子树中的左叶子之和”。

---

第3段：判断当前节点的左孩子（核心！）

java

int midValue = 0; if (root.left != null && root.left.left == null && root.left.right == null) { midValue = root.left.val; }

这是本题的核心逻辑：

• root.left != null：当前节点有左孩子

• root.left.left == null：左孩子没有左孙子

• root.left.right == null：左孩子没有右孙子

满足这三个条件 → 左孩子就是左叶子！

---

第4段：返回总和

java

return midValue + leftSum + rightSum;

将三部分相加：

• midValue：当前节点的左叶子值

• leftSum：左子树中的左叶子之和

• rightSum：右子树中的左叶子之和

leftSum和midValue不冲突，它们计算的是不同层级的“左叶子”。

• leftSum：计算的是左子树内部所有左叶子的和（比如孙子、曾孙子）

• midValue：计算的是当前节点的左孩子是不是左叶子

它们是互补的，不是重复的。

---

具体例子

text

3 / \ 9 20 / \ 15 7

站在节点 3的角度：

变量	计算什么	包含哪些左叶子
leftSum	左子树（节点9）中所有左叶子	节点9的子树中：没有（9没有孩子）→ 0
rightSum	右子树（节点20）中所有左叶子	节点20的子树中：15（因为15是20的左孩子且是叶子）→ 15
midValue	节点3的左孩子（节点9）是不是左叶子	9是叶子 ✅ → 9

结果：9 + 0 + 15 = 24

---

leftSum不包括当前节点的直接左孩子。

• leftSum= 递归调用sumOfLeftLeaves(root.left)

• 这个递归会进入左子树，站在左子树的根节点（9）重新开始计算

• 在节点9的视角里，它计算的是它的左孩子（null）是不是左叶子

• 节点9不会把自己算进去（因为站在节点9的角度，它不知道自己是父节点的左孩子）

关键：节点9作为左叶子，是被它的父节点（3）的midValue加上的，不是被它自己加上的。

---

节点3 │ ┌────────────┼────────────┐ │ │ │ leftSum rightSum midValue (递归进9) (递归进20) (直接判断左孩子9) │ │ │ ↓ ↓ ↓ 节点9自己 节点20自己 节点9的值被加上 不会加自己 判断左孩子15 （因为9是左叶子）

整体来看这个过程，对于初学者并不是很友好，很难正确的理解递归的每一步，简单的来说就是从头开始执行，在这个方法中再次执行到这个方法时，继续从头开始，直到得到一个结果时，才继续向下面执行，循环往复，稍微不注意，就会被搞混，但是对于代码来说就是一行的事，重在理解。

广度优先搜索（BFS，层序遍历）

完整执行过程

初始化

java

queue = [] // 空队列 ans = 0

第1步：放入根节点

java

queue.offer(root); // queue = [3]

第2步：进入 while 循环 —— 处理节点 3

java

node = queue.poll(); // 取出 3，queue = []

检查 node.left（节点9）：

• node.left != null✅

• isLeaf(9)？9.left == null 且 9.right == null → ✅ 是叶子

• 所以ans += 9→ans = 9

• 注意：9 是叶子，不放入队列（不需要再遍历它的子节点）

检查 node.right（节点20）：

• node.right != null✅

• isLeaf(20)？20.left = 15（不为 null）→ ❌ 不是叶子

• 所以queue.offer(20)→queue = [20]

此时状态：

text

ans = 9 queue = [20]

第3步：处理节点 20

java

node = queue.poll(); // 取出 20，queue = []

检查 node.left（节点15）：

• node.left != null✅

• isLeaf(15)？15.left == null 且 15.right == null → ✅ 是叶子

• 所以ans += 15→ans = 9 + 15 = 24

• 15 是叶子，不放入队列

检查 node.right（节点7）：

• node.right != null✅

• isLeaf(7)？7.left == null 且 7.right == null → ✅ 是叶子

• ⚠️ 注意：7 是右孩子，不可能是左叶子，所以不加到 ans

• 但 7 是叶子，不放入队列

此时状态：

text

ans = 24 queue = []

第4步：循环结束

java

while (!queue.isEmpty()) // queue = []，退出循环 return ans; // 返回 24

text

┌─────────────────────────────────────────────────────────────┐ │ 初始化 │ │ queue = [3], ans = 0 │ └─────────────────────────────────────────────────────────────┘ ↓ ┌─────────────────────────────────────────────────────────────┐ │ 第1轮循环：处理节点 3 │ │ │ │ 取出 3，queue = [] │ │ │ │ 检查左孩子 9： │ │ ├─ 9 是叶子吗？ ✅ │ │ └─ ans += 9 → ans = 9 │ │ （9 不加入队列） │ │ │ │ 检查右孩子 20： │ │ ├─ 20 是叶子吗？ ❌（有孩子） │ │ └─ queue.offer(20) → queue = [20] │ │ │ │ 本轮结束：ans = 9, queue = [20] │ └─────────────────────────────────────────────────────────────┘ ↓ ┌─────────────────────────────────────────────────────────────┐ │ 第2轮循环：处理节点 20 │ │ │ │ 取出 20，queue = [] │ │ │ │ 检查左孩子 15： │ │ ├─ 15 是叶子吗？ ✅ │ │ └─ ans += 15 → ans = 24 │ │ （15 不加入队列） │ │ │ │ 检查右孩子 7： │ │ ├─ 7 是叶子吗？ ✅ │ │ └─ 但 7 是右孩子，不加 ans │ │ （7 不加入队列） │ │ │ │ 本轮结束：ans = 24, queue = [] │ └─────────────────────────────────────────────────────────────┘ ↓ ┌─────────────────────────────────────────────────────────────┐ │ 循环结束，返回 ans = 24 │ └─────────────────────────────────────────────────────────────┘

关键点总结

1. BFS 如何处理左叶子

• 不是在叶子节点自己判断（叶子不知道自己是左还是右）

• 而是在父节点判断：if (node.left != null && isLeaf(node.left))

2. 为什么右孩子要加入队列

虽然右孩子本身不可能是左叶子，但右孩子的子树中可能有左叶子。

text

3 \ 20 / 15 ← 15 是左叶子（在右子树中）

所以必须把非叶子的右孩子也加入队列继续遍历。

3. 为什么右孩子是叶子就不加入队列

java

if (node.right != null && !isLeaf(node.right)) { queue.offer(node.right); }

• 如果右孩子是叶子 → 不可能是左叶子 → 不需要处理它的子节点（没有）→ 不加入队列

• 如果右孩子不是叶子 → 它的子树中可能有左叶子 → 加入队列继续遍历

4. BFS vs 递归对比

总结

BFS 解法：用队列按层遍历每个节点，在访问父节点时检查它的左孩子是不是叶子，是就累加，不是就把左孩子（非叶子）和右孩子（非叶子）加入队列继续遍历。

题目答案：

java class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int ans = 0; while (!queue.isEmpty()) { TreeNode node = queue.poll(); // 检查左孩子 if (node.left != null) { if (isLeaf(node.left)) { ans += node.left.val; // 左叶子，直接加 } else { queue.offer(node.left); // 不是叶子，继续遍历 } } // 检查右孩子（右孩子本身不可能是左叶子，但它的子树中可能有） if (node.right != null && !isLeaf(node.right)) { queue.offer(node.right); } } return ans; } private boolean isLeaf(TreeNode node) { return node.left == null && node.right == null; } }

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int sumOfLeftLeaves(TreeNode root) { // 边界条件：空树返回0 if (root == null) { return 0; } // 递归计算左子树的左叶子之和 int leftSum = sumOfLeftLeaves(root.left); // 递归计算右子树的左叶子之和 int rightSum = sumOfLeftLeaves(root.right); // 核心：判断当前节点的左孩子是不是左叶子 int midValue = 0; if (root.left != null && root.left.left == null && root.left.right == null) { midValue = root.left.val; // 左孩子是左叶子，加上它的值 } // 返回总和 return midValue + leftSum + rightSum; } }

结语：如果对你有帮助，请点赞，关注，收藏，你的支持就是我最大的鼓励！