LeetCode 404.左叶子之和的递归求解：终止条件与递归逻辑的深度剖析

一、题目解析：左叶子的定义与递归求解思路

题目描述

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

关键要点拆解

1. 左叶子的双重条件：
   • 必须是父节点的左子节点；
   • 自身必须是叶子节点（左右子节点均为空）。
2. 递归求解核心：
   • 后序遍历思想：先递归处理子树，再处理当前节点；
   • 状态传递：通过递归返回值传递子树中的左叶子和；
   • 条件判断：在递归返回后判断当前节点的左子节点是否为左叶子。

示例说明

对于二叉树：

    3/ \9  20/  \15   7

左叶子为9和15，和为24。其中：

• 9是3的左子节点且为叶子节点；
• 15是20的左子节点且为叶子节点。

二、递归算法的核心要素：终止与递归条件

完整代码

/*** 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) {if (root == null) return 0;if (root.left == null && root.right == null) {return 0;}int leftSum = sumOfLeftLeaves(root.left);if (root.left != null && root.left.left == null && root.left.right == null) {leftSum = root.left.val;}int rightSum = sumOfLeftLeaves(root.right);return leftSum + rightSum;}
}

核心要素一：终止条件设计

1. 空节点终止（base case 1）

if (root == null) return 0;

• 逻辑：空树中没有左叶子，直接返回0。
• 作用：避免空指针异常，作为递归的最底层返回值。

2. 叶子节点终止（base case 2）

if (root.left == null && root.right == null) {return 0;
}

• 逻辑：叶子节点本身不是左叶子（左叶子需要有父节点），返回0。
• 误区说明：有人可能认为叶子节点应返回自身值，但左叶子的定义依赖父节点，单独的叶子节点（如根节点）不符合左叶子条件。

核心要素二：递归条件设计

1. 左子树递归与左叶子判断

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

• 先递归后判断的原因：
  1. 递归调用sumOfLeftLeaves(root.left)先获取左子树中的左叶子和；
  2. 递归返回后，当前节点已知道左子节点的状态（是否为叶子），此时判断root.left是否为左叶子；
  3. 若root.left是左叶子，则用其值覆盖递归返回的左子树和（因为左子树和中不包含当前节点的左叶子，需单独累加）。

2. 右子树递归

int rightSum = sumOfLeftLeaves(root.right);

• 逻辑：递归计算右子树中的左叶子和，右子树的左叶子判断在右子树的递归过程中完成。

三、递归流程深度解析：为什么先递归再赋值？

1. 递归调用与状态传递

递归调用链

sumOfLeftLeaves(root)↓
sumOfLeftLeaves(root.left)  // 先处理左子树↓
sumOfLeftLeaves(root.left.left)  // 递归到左子树的左子树↓
...（直到叶子节点，返回0）

• 状态传递：递归返回值从底层叶子节点向上传递，每层处理当前节点的左叶子判断。

2. 左叶子赋值的时机分析

错误顺序假设（先判断后递归）

if (root.left是左叶子) {leftSum = root.left.val;
} else {leftSum = sumOfLeftLeaves(root.left);
}

• 问题：若先判断再递归，会导致：
  1. 无法获取左子树内部的左叶子和；
  2. 若root.left不是左叶子，其内部可能还有左叶子，需递归计算。

正确顺序（先递归后判断）

leftSum = sumOfLeftLeaves(root.left);  // 先获取左子树的左叶子和
if (root.left是左叶子) {leftSum = root.left.val;  // 覆盖为当前左叶子的值
}

• 逻辑优势：
  1. leftSum初始为左子树的左叶子和；
  2. 若当前节点的左子节点是左叶子，则用其值替换（因为左子树的和不包含当前左叶子，需单独处理）；
  3. 若当前节点的左子节点不是左叶子，则leftSum保持为左子树的和，正确累加。

四、递归流程模拟：以示例二叉树为例

示例二叉树结构

    3/ \9  20/  \15   7

递归调用过程

1. 根节点3的处理：

   • 递归调用sumOfLeftLeaves(9)（左子树）；
   • 9是叶子节点，返回0；
   • 判断9是否为左叶子（是），leftSum=9；
   • 递归调用sumOfLeftLeaves(20)（右子树）。

2. 节点20的处理：

   • 递归调用sumOfLeftLeaves(15)（左子树）；
   • 15是叶子节点，返回0；
   • 判断15是否为左叶子（是），leftSum=15；
   • 递归调用sumOfLeftLeaves(7)（右子树）；
   • 7是叶子节点，返回0；
   • rightSum=0；
   • 返回15+0=15。

3. 根节点3的最终计算：

   • leftSum=9，rightSum=15；
   • 返回9+15=24。

五、递归算法的复杂度分析与优化思考

1. 时间复杂度

• O(n)：每个节点仅访问一次，n为节点数。
• 原因：递归过程中每个节点被访问一次，无重复计算。

2. 空间复杂度

• O(h)：h为树的高度，取决于递归栈深度。
• 最坏情况：树退化为链表时，h=n，空间复杂度O(n)。

3. 递归与迭代的对比

方法	优点	缺点
递归	代码简洁，逻辑直观	可能栈溢出
迭代	空间可控，适合大数据	代码复杂，需手动维护栈

4. 优化建议

• 尾递归优化：Java不支持尾递归优化，但可通过改写递归为迭代避免栈溢出；
• 剪枝优化：若已知某子树无左叶子，可提前返回0，减少递归深度。

六、总结：递归算法的设计哲学

1. 终止条件的设计原则

• 最小子问题：明确最底层的返回值（空树、叶子节点返回0）；
• 无重复判断：终止条件需覆盖所有无需继续递归的情况。

2. 递归条件的核心思想

• 分治思想：将问题分解为左子树和右子树的子问题；
• 状态传递：通过返回值传递子问题的解，在父问题中合并；
• 延迟判断：先递归获取子树状态，再根据子树状态处理当前节点。

3. 左叶子判断的关键

• 依赖关系：左叶子的判断依赖父节点，因此必须在父节点的递归层处理；
• 时机选择：在获取子树的左叶子和之后，判断当前节点的左子节点是否为左叶子，确保不遗漏也不重复。

这种递归解法充分体现了“自顶向下，先递归后判断”的设计思想，通过递归的天然分层特性，将左叶子的判断分散到各层处理，既保证了逻辑的清晰性，又实现了问题的高效求解。理解这种递归设计模式，对解决类似的树结构问题（如子树和、深度计算等）具有重要的借鉴意义。