LeetCode 404.左叶子之和的迭代求解：栈结构与父节点定位的深度解析

一、题目解析：左叶子的定义与问题本质

题目描述

LeetCode 404. 左叶子之和要求计算二叉树中所有左叶子节点的值之和。左叶子的定义是：如果一个节点是其父节点的左子节点，并且它本身没有左右子节点，则称为左叶子。

关键要点

1. 左叶子的双重条件：
   • 必须是父节点的左子节点；
   • 自身没有子节点（左右子节点均为空）。
2. 问题本质：需要在遍历二叉树的过程中，判断每个节点是否为左叶子，并累加其值。

示例说明

对于二叉树：

    3/ \9  20/  \15   7

左叶子为9和15，和为24。

二、迭代解法核心：栈结构与父节点定位逻辑

代码实现

/*** 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) {Stack<TreeNode> cur = new Stack<>();if (root == null) {return 0;}int res = 0;TreeNode temp = root;cur.push(root);while (!cur.empty()) {temp = cur.pop();// 检查左子节点是否为左叶子if (temp.left != null && temp.left.left == null && temp.left.right == null) {res += temp.left.val;}// 先压右子节点，再压左子节点（保证左子树先处理）if (temp.right != null) {cur.push(temp.right);}if (temp.left != null) {cur.push(temp.left);}}return res;}
}

核心设计解析：为什么选择栈结构？

1. 栈的特性与深度优先遍历

• 栈的后进先出（LIFO）特性天然适合深度优先遍历（DFS）：
  • 先压入右子节点，再压入左子节点，确保左子树先于右子树处理；
  • 模拟递归调用栈的行为，避免递归可能导致的栈溢出。

2. 栈中存储父节点的必要性

• 左叶子的判断依赖于父节点：
  • 必须通过父节点才能确定当前节点是否为左子节点；
  • 栈中存储的是父节点，而非当前叶子节点，因此可以直接通过temp.left判断左子节点是否为叶子。

三、父节点定位左叶子的逻辑深度解析

1. 左叶子的判断条件

if (temp.left != null && temp.left.left == null && temp.left.right == null) {res += temp.left.val;
}

• 条件拆解：
  1. temp.left != null：父节点存在左子节点；
  2. temp.left.left == null：左子节点没有左子节点；
  3. temp.left.right == null：左子节点没有右子节点。
• 逻辑本质：通过父节点temp判断其左子节点是否为叶子节点，满足条件则累加值。

2. 栈操作顺序与遍历顺序

if (temp.right != null) {cur.push(temp.right);
}
if (temp.left != null) {cur.push(temp.left);
}

• 入栈顺序：先右子节点，后左子节点；
• 出栈顺序：先左子节点，后右子节点（LIFO）；
• 效果：实现深度优先遍历中的先左后右顺序，与递归的前序遍历一致。

3. 栈操作模拟：以示例二叉树为例

示例二叉树：

    3/ \9  20/  \15   7

栈操作流程：

1. 初始状态：
   栈：[3]，结果res=0

2. 第一次循环：

   • 弹出3，检查左子节点9：
     9是3的左子节点，且9没有子节点，累加9，res=9；
   • 压入右子节点20，左子节点9（已处理，无需重复处理？不，此处压入的是父节点的子节点）；
     栈：[20, 9]

3. 第二次循环：

   • 弹出9，检查左子节点（9的左子节点为空），无操作；
   • 压入9的右子节点（空），左子节点（空）；
     栈：[20]

4. 第三次循环：

   • 弹出20，检查左子节点15：
     15是20的左子节点，且15没有子节点，累加15，res=24；
   • 压入20的右子节点7，左子节点15；
     栈：[7, 15]

5. 第四次循环：

   • 弹出15，检查左子节点（空），无操作；
   • 压入15的右子节点（空），左子节点（空）；
     栈：[7]

6. 第五次循环：

   • 弹出7，检查左子节点（空），无操作；
   • 压入7的右子节点（空），左子节点（空）；
     栈：空

7. 最终结果：res=24

四、栈结构的核心作用：模拟递归与状态维护

1. 迭代与递归的等价性

递归实现	迭代栈实现
系统自动维护调用栈	手动维护栈保存节点
代码简洁但可能栈溢出	代码直观且栈深度可控
隐式保存父节点上下文	显式通过父节点判断叶子

2. 时间与空间复杂度分析

• 时间复杂度：O(n)，每个节点仅访问一次；
• 空间复杂度：O(h)，h为树的高度，最坏情况下（链表树）为O(n)。

3. 大厂面试中的考点分析

• 栈的选择：考察对数据结构特性的理解（LIFO适合DFS）；
• 父节点定位：考察对左叶子定义的理解（必须通过父节点判断）；
• 迭代与递归转换：考察算法实现的灵活性。

五、左叶子判断的常见误区与优化

1. 常见误区

• 误判非左子节点为左叶子：
  仅判断节点是否为叶子，忽略“左子节点”的条件。例如：

  if (node.left == null && node.right == null) { // 错误，未判断是否为左子节点res += node.val;
  }
  

2. 优化方向：层序遍历（BFS）实现

public int sumOfLeftLeaves(TreeNode root) {if (root == null) return 0;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int res = 0;while (!queue.isEmpty()) {TreeNode node = queue.poll();if (node.left != null) {// 左子节点是叶子if (node.left.left == null && node.left.right == null) {res += node.left.val;} else {queue.offer(node.left);}}if (node.right != null) {queue.offer(node.right);}}return res;
}

• 对比：
  • 时间复杂度相同（O(n)）；
  • 空间复杂度可能更高（队列平均宽度可能大于栈深度）；
  • 代码逻辑更直观，适合初学者理解。

3. 极端情况处理

• 单节点树：根节点不是左叶子（无父节点），返回0；
• 只有右子树：所有叶子均非左叶子，返回0；
• 完全左斜树：所有左子节点若为叶子则累加，如树1->2->3->4，左叶子为2、3、4，和为9。

六、总结：迭代法求解左叶子之和的核心要点

1. 栈结构的双重作用

• 作为遍历容器，实现深度优先搜索；
• 保存父节点，为左叶子判断提供上下文。

2. 左叶子判断的关键

• 必须同时满足“左子节点”和“叶子节点”两个条件；
• 通过父节点的left指针访问左子节点，判断其是否为叶子。

3. 算法设计的核心思想

• 状态维护：栈中保存的是父节点状态，而非叶子节点；
• 遍历顺序：通过栈的入栈顺序控制遍历顺序，实现深度优先；
• 条件过滤：在遍历过程中实时判断左叶子，避免额外存储。

这种迭代解法充分展示了栈结构在树遍历中的灵活性——通过维护父节点状态，精准定位左叶子节点。理解这种“父节点定位”的思想，对解决类似需要依赖上下文的树节点问题（如求祖父节点值、子树和等）具有重要的借鉴意义。在实际工程中，迭代法因避免递归栈溢出，更适合处理大规模树结构，是大厂面试中需要重点掌握的技能。