算法►二叉树

二叉树的最近公共祖先（LCA）问题总结

本文围绕三道经典 LCA 题目：
236. 二叉树的最近公共祖先、
235. 二叉搜索树的最近公共祖先、
1123. 所有最深叶节点的最近公共祖先
系统总结最近公共祖先解题思路

一、什么是最近公共祖先（LCA）

最近公共祖先（Lowest Common Ancestor） 指的是：

在一棵树中，两个节点 p 和 q 的所有公共祖先中，离它们最近的那个节点。

直观做题时，我们通常是：

  1. 找到 p 和 q
  2. 从它们向上回溯
  3. 第一个相交的节点就是答案

而在代码中，这个“向上回溯”的过程，天然适合用 递归 来表达。

二、236. 二叉树的最近公共祖先（母模板）

一句话思路

在左右子树中分别查找 p 和 q，
如果左右都找到了，当前节点就是最近公共祖先。

递归分类讨论

对于当前节点 root：

  1. root == null

    • 返回 null（没找到）

  2. root == p 或 root == q

    • 直接返回当前节点
    • 因为最近公共祖先不可能在它的子树下面

  3. 递归左右子树

    1
    2
    left = LCA(root.left)
    right = LCA(root.right)
    • left != null && right != null
      p、q 分别在左右子树中，root 就是 LCA
    • 只有一边非空：表示 q、p 都在非空边，直接返回非空节点，即是答案

本质理解

  • 递（向下）：定位 p、q
  • 归（向上）：判断当前节点是否“第一次同时覆盖目标”

这是后面所有 LCA 题目的核心模板

三、235. 二叉搜索树的最近公共祖先（BST 优化）

与 236 的关键区别

235 给的是 二叉搜索树（BST），多了一个重要信息：

左子树所有值 < 根节点 < 右子树所有值

利用 BST 性质剪枝

设当前节点为 root：

  1. root.val > p.val && root.val > q.val
    两个节点一定在 左子树
  2. root.val < p.val && root.val < q.val
    两个节点一定在 右子树
  3. 否则
    一个在左，一个在右（或 root 本身）
    当前节点就是最近公共祖先

小结

题目 是否需要遍历整棵树 关键依据
236 是 普通二叉树
235 否 BST 有序性

235 是 236 在 BST 场景下的剪枝优化版

四、1123. 所有最深叶节点的最近公共祖先（难点）

初始直觉（两次遍历）

我的第一反应是：

  1. 先遍历整棵树，找到所有最深的叶子节点
  2. 再利用 236 的思路，求这些节点的最近公共祖先

这个思路完全正确，但本质是 两次遍历，并不优雅。

思路优化

在查看参考答案后，我意识到：

  • 如果最深叶节点只存在于左子树：最近公共祖先一定在左子树
  • 如果左右子树都存在最深叶节点，且深度相同：当前节点才可能成为答案

这说明：

答案一在递归过程中就可以产生的

五、两种递归设计思路

思路一：自顶向下（参数传递）

  • 向下递归时传递当前深度
  • 使用全局变量维护最大深度
  • 当左右子树深度相等，且等于全局最大深度时，更新答案（这里的答案会变，因为随着遍历最大深度会变）

思路二（推荐）：自底向上（返回值回溯）

进一步抽象问题后，可以把 1123 完全转化为一个分治问题：

每棵子树只需要向父节点返回两件事：

  1. 子树的最大深度
  2. 子树中最深叶节点的最近公共祖先

六、自底向上的核心合并逻辑（重点）

设当前节点 root：

  • 左子树返回 (depthL, lcaL)
  • 右子树返回 (depthR, lcaR)

返回值表示当前节点为根的树的深度与最深叶子节点的最近公共祖先节点

情况 1：左子树更深

1
depthL > depthR

所有最深叶节点都在左子树

最近公共祖先也一定在左子树

返回 (depthL + 1, lcaL)

情况 2：左右子树深度相等

1
depthL == depthR
  • 最深叶节点分布在左右子树
  • 当前节点是第一次“同时覆盖”它们的节点
  • 当前节点就是最近公共祖先
  • 返回 (depthL + 1, root)

七、为什么要用 Pair / 二元组，而不是 Map？

在 1123 的自底向上实现中，递归函数需要返回：

  • 一个 int（深度）
  • 一个 TreeNode（最近公共祖先）

这两个值：

  • 没有 key → value 的映射关系
  • 但 有固定顺序和明确语义

因此它们本质上是一个 有位置关系的二元组：

1
(depth, lca)

使用 Pair（或自定义类）比 Map 更贴合问题本质，也更清晰、简洁。

八、从 236 到 1123：思路的统一

可以这样理解：

  • 236：判断左右子树是否分别找到了 p 和 q
  • 1123：判断左右子树是否分别包含“最深叶节点”

本质上，1123 是对 236 思路的自然推广：

把“是否找到目标节点”升级成了“子树是否达到最深深度”

九、递归设计的两大核心原则（重要总结）

向下传递 —— 参数传递法（递）

适用场景

  • 深度
  • 路径状态
  • 累计信息

特点

  • 信息从父节点流向子节点
  • 子节点无法反向影响父节点

向上返回 —— 返回值回溯法（归）

适用场景

  • 子树高度
  • 子树统计信息
  • 最近公共祖先

特点

  • 信息从子节点汇总到父节点
  • 父节点基于左右子树返回值做决策

十、总结

  • 236：最近公共祖先的母模板，理解递归回溯的经典题
  • 235：利用 BST 性质进行剪枝优化
  • 1123：递归设计能力的分水岭，考验信息如何在递归中流动

二叉树问题的核心，不是“怎么写递归”，
而是“你希望子树返回什么信息”

一旦子问题定义清晰，答案就会在回溯过程中自然浮现。

相关代码

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