当前位置：首页 > news >正文

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

news 2025/5/23 6:17:10

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

题目描述

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

关键要点

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

示例说明

对于二叉树：

    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

栈操作流程：

初始状态：
栈：[3]，结果res=0
第一次循环：
- 弹出3，检查左子节点9：
  9是3的左子节点，且9没有子节点，累加9，res=9；
- 压入右子节点20，左子节点9（已处理，无需重复处理？不，此处压入的是父节点的子节点）；
  栈：[20, 9]
第二次循环：
- 弹出9，检查左子节点（9的左子节点为空），无操作；
- 压入9的右子节点（空），左子节点（空）；
  栈：[20]
第三次循环：
- 弹出20，检查左子节点15：
  15是20的左子节点，且15没有子节点，累加15，res=24；
- 压入20的右子节点7，左子节点15；
  栈：[7, 15]
第四次循环：
- 弹出15，检查左子节点（空），无操作；
- 压入15的右子节点（空），左子节点（空）；
  栈：[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;
}