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

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

题目描述

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

关键要点拆解

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

示例说明

对于二叉树：

左叶子为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的处理：
- 递归调用sumOfLeftLeaves(9)（左子树）；
- 9是叶子节点，返回0；
- 判断9是否为左叶子（是），leftSum=9；
- 递归调用sumOfLeftLeaves(20)（右子树）。
节点20的处理：
- 递归调用sumOfLeftLeaves(15)（左子树）；
- 15是叶子节点，返回0；
- 判断15是否为左叶子（是），leftSum=15；
- 递归调用sumOfLeftLeaves(7)（右子树）；
- 7是叶子节点，返回0；
- rightSum=0；
- 返回15+0=15。
根节点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. 左叶子判断的关键

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

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

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