算法►二叉树►递归

leetcode 解题总结：二叉树：相同、对称、平衡、右视图

刷题范围

  • 基础题
      1. 相同的树
      1. 对称二叉树
      1. 平衡二叉树
      1. 二叉树的右视图
  • 扩展题
    • 965、954、226、617、2331、508、1026、1372、1080

一、核心认知：二叉树递归的本质

1. 递归遍历 ≈ 访问每一个节点

二叉树的递归遍历，本质上就是：

对每一个节点做一次访问，并在访问过程中完成题目要求的逻辑

我对「递归拆分子问题」的理解：

  • 把对当前节点的处理逻辑抽出来
  • 把对子树的处理交给“规模更小的同一问题”

2. 递归的核心模板

1
2
3
4
5
6
7
8
9
10
11
12
13
dfs(node):
    if node == null:
        return base

    // 1. 处理当前节点（可选）
    ...

    // 2. 递归访问左右子树
    left = dfs(node.left)
    right = dfs(node.right)

    // 3. 归并左右子树结果
    return combine(left, right)

是否“处理当前节点”在前还是在后，决定了是自顶向下还是自底向上

二、“递” 与 “归”的清晰区分（今天最大的收获）

1. 什么是「递」？

递 = 分解问题、向下传递信息

  • 从根节点向下
  • 信息是已知的、确定的
  • 常见传递内容：
    • 路径和
    • 最大值 / 最小值
    • 深度、层数
    • 父节点信息

典型特征： 函数参数在变，状态向下传

2 什么是「归」？

归 = 汇总结果、向上返回信息

  • 从叶子节点向上
  • 信息是子树计算后的结果
  • 常见返回内容：
    • 高度
    • 是否平衡
    • 最大/最小路径
    • 子树统计信息

典型特征：返回值在变，状态向上合并

3. 自顶向下 vs 自底向上

方式 特点 类比遍历 适合场景
自顶向下 先处理当前节点，再递 先序 路径和、区间限制
自底向上 先递归子树，再归 后序 高度、平衡性

自顶向下更符合直觉，自底向上是动态规划的基础

三、做复杂题时的通用策略

1. 简化递归逻辑

当题目逻辑变复杂时：

  • 不要把所有判断写在一层
  • 可以：利用 返回值 或 **全局变量 **或 多返回信息（包装类 / 数组）

递归只负责“计算”，答案在递归结束后统一处理

2. map.merge 的实战体会

1
map.merge(key, 1, Integer::sum);

含义总结：

  • key 不存在 → 新建 (key, newValue)
  • key 存在 → (oldValue, newValue) 传入函数，返回新值

在：

    1. 出现次数最多的子树元素和

    这类「统计 + DFS」题中非常合适

四、典型题目的方法论总结

1. 1026. 节点与其祖先之间的最大差值

核心体会：

  • 分开体现了 递（向下传 max / min） 与 **归（返回结果）**两种方法都可行
  • 是理解「递归双向信息流」的经典题

2. 1372. 二叉树中的最长交错路径

关键点：

  • 递归过程中需要重置变量
  • 每个节点都可能作为新的起点
  • 状态不是简单继承，而是条件性重置

3. 1080. 根到叶路径上的不足节点（重要）

这是今天**“递 + 归”**结合体会最深的一题。

  • **递（向下）**传递：从根到当前节点的路径和
  • **归（向上）**汇总：包含该节点的所有根到叶路径
  • 中间逻辑
    • 判断当前节点是否是「不足节点」

真正体会到：

递负责携带历史信息，归负责判断整体价值

五、关于递归与迭代的一个重要认知

只有“递下去”的过程，才可能转成迭代
“归上来”的过程，本质依赖系统栈，无法直接用迭代模拟

  • BFS / DFS（只向下）→ 可迭代
  • 后序遍历 / 动态规划式递归 → 难以完全转迭代

这是理解「为什么有些递归不能改成 while」的关键。

六、今日整体收获总结

  • 二叉树问题的本质是：节点访问 + 信息流动
  • 真正重要的不是“会不会写递归”，而是：
    • 信息是 向下传 还是 向上收
    • 答案是在 途中产生 还是 最终汇总
  • 自顶向下更直观，自底向上是进阶算法（DP、树 DP）的必经之路

七、相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。