目录
一、LeetCode 236. 普通二叉树的最近公共祖先
1. 核心思想：后序遍历 + 递归分治（验证式遍历）
2. 完整实现代码
3. 重点 & 难点
重点：递归返回值的 “信号含义”（核心！）
难点：
4. 深度分析
二、LeetCode 235. 二叉搜索树（BST）的最近公共祖先
1. 核心思想：有序性预判 + 单向递归（预判式遍历）
2. 完整实现代码
3. 重点 & 难点
重点：BST 有序性带来的 “剪枝” 优化
难点：
4. 深度分析
三、两道题的核心对比
四、通用易错点总结
1. 236 题高频易错点
2. 235 题高频易错点
3. 通用易错点
五、深度总结
最近公共祖先（LCA）是二叉树领域的经典高频题，LeetCode 236（普通二叉树的 LCA）和 235（二叉搜索树 BST 的 LCA）是同类型但解法差异极大的两道题 —— 核心差异源于 BST 的 “数值有序性”：235 可通过有序性 “预判 LCA 位置” 实现单向递归剪枝，236 无特性可利用，只能通过 “后序遍历 + 递归分治” 验证子树存在性。以下从核心思路、实现、重难点、深度分析等维度全面总结。
一、LeetCode 236. 普通二叉树的最近公共祖先
1. 核心思想：后序遍历 + 递归分治（验证式遍历）
普通二叉树无 “有序性” 等特殊性质，无法预判 LCA 位置，因此采用后序遍历的递归分治（先子后根）：
- 递归终止条件：遇到空节点（返回 null，子树无 p/q）、遇到 p/q（返回自身，找到目标节点）；
- 信号传递：递归左、右子树，获取 “左子树是否找到 p/q”“右子树是否找到 p/q” 的信号；
- 分治合并：根据左右子树的信号，判断当前节点是否为 LCA。
2. 完整实现代码
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 终止条件1：空节点（子树无p/q，返回null） if (root == null) return null; // 终止条件2：找到p/q（自身是祖先，返回自身） if (root == p || root == q) return root; // 后序遍历：先处理左、右子树，获取信号 TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); // 分治合并逻辑 if (left != null && right != null) return root; // 左右都找到→当前是LCA return left != null ? left : right; // 单侧找到/都没找到（题目保证存在，后者仅子树出现） } }3. 重点 & 难点
重点：递归返回值的 “信号含义”（核心！）
递归返回值不是直接返回 LCA，而是 “当前子树是否存在 p/q” 的信号：
| 返回值 | 含义 |
|---|---|
| null | 当前子树既无 p 也无 q |
| p/q | 当前子树仅找到 p 或仅找到 q |
| 非 p/q 的节点 | 当前子树同时找到 p 和 q（当前节点是 LCA） |
难点：
- 为什么必须用后序遍历？只有先获取左、右子树的 “找到信号”，才能判断当前节点是否是 LCA—— 前序 / 中序遍历无法完成 “子树信号合并”，这是递归逻辑的唯一选择。
- 容易混淆 “返回 p/q” 和 “返回 LCA”：递归到 p 节点时返回 p，不是因为 p 是 LCA，而是告诉上层 “这侧找到了 p”；只有当左右子树都返回非 null 时，才确定当前节点是 LCA。
4. 深度分析
- 时间复杂度：O (n)（n 为节点数）。普通二叉树无特性，最坏情况（斜树）需遍历所有节点；
- 空间复杂度：O (h)（h 为树高）。递归调用栈深度 = 树高，平衡树 h=logn，斜树 h=n；
- 核心逻辑本质：“自底向上” 的信号传递 —— 底层子树的 “找到信号” 向上汇总，直到某一层节点满足 “左右都找到”，该节点就是 LCA。
二、LeetCode 235. 二叉搜索树（BST）的最近公共祖先
1. 核心思想：有序性预判 + 单向递归（预判式遍历）
BST 的核心特性是 “左子树所有节点 < 根 < 右子树所有节点”，因此可通过数值比较直接预判 LCA 位置，无需遍历整棵树：
- 若 p、q 都 < root.val：LCA 在左子树→仅递归左子树；
- 若 p、q 都 > root.val：LCA 在右子树→仅递归右子树；
- 其他情况（p≤root≤q 或 q≤root≤p，或 root=p/q）：当前 root 就是 LCA→直接返回，递归终止。
2. 完整实现代码
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { // 情况1：p/q都在左子树→递归左 if (p.val < root.val && q.val < root.val) { return lowestCommonAncestor(root.left, p, q); } // 情况2：p/q都在右子树→递归右 else if (p.val > root.val && q.val > root.val) { return lowestCommonAncestor(root.right, p, q); } // 情况3：其余情况→当前root是LCA else { return root; } } }3. 重点 & 难点
重点：BST 有序性带来的 “剪枝” 优化
普通二叉树是 “验证式遍历”（遍历子树验证是否存在 p/q），而 BST 是 “预判式遍历”（通过数值比较直接定位 LCA 路径），遍历范围从 “整棵树” 缩减为 “根到 LCA 的单条路径”，时间复杂度从 O (n) 降至 O (h)（平衡 BST 下 O (logn)）。
难点：
- 隐性的递归终止条件：题目保证 p/q 存在，因此递归不会遍历到空节点，终止条件藏在 “情况 3” 中（返回 root）；新手易冗余添加
if (root == null) return null，该判断无性能收益（永远不触发），仅提升工程健壮性。 - “其他情况” 的覆盖范围：不仅包含 “p/q 分属左右子树”，还包含 “root 是 p/q 其中一个”（节点可作为自身的祖先），漏考虑后者会导致逻辑错误。
4. 深度分析
- 时间复杂度：O (h)（h 为树高）。仅遍历根到 LCA 的路径，无无效节点访问；
- 空间复杂度：O (h)（递归栈深度 = 路径长度）；
- 迭代版优化（避免递归栈溢出）
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (true) { if (p.val < root.val && q.val < root.val) root = root.left; else if (p.val > root.val && q.val > root.val) root = root.right; else return root; } } }
三、两道题的核心对比
| 维度 | LeetCode 236（普通二叉树） | LeetCode 235（BST） |
|---|---|---|
| 核心思路 | 后序遍历 + 递归分治（验证存在性） | 有序性预判 + 单向递归（定位位置） |
| 递归终止条件 | 显式（root==null /root==p/q） | 隐性（情况 3 返回 root） |
| 遍历范围 | 整棵树（最坏 O (n)） | 根到 LCA 的路径（O (h)） |
| 关键依赖 | 仅依赖二叉树递归结构 | 依赖 BST 的数值有序性（核心） |
| 分支逻辑 | 合并左、右子树信号（3 种情况） | 数值比较预判方向（3 种情况） |
| 代码复杂度 | 中等（需理解信号传递） | 简单（仅数值比较） |
四、通用易错点总结
1. 236 题高频易错点
- 误解递归返回值：把 “返回 p/q” 当成 “返回 LCA”，忽略 “信号传递” 的本质；
- 遗漏
root == null终止条件：递归到空节点的子节点，触发空指针异常；- 分支逻辑错误：把 “左右都非 null 返回 root” 写成 “返回 left/right”，导致 LCA 判断错误；
- 忽略 “节点可作为自身祖先”：比如 p 是 q 的祖先时，直接返回 p 即可，无需继续递归。
2. 235 题高频易错点
- 冗余添加
root == null判断：题目保证 p/q 存在，该判断永远不触发，无性能收益；- 数值比较逻辑错误：把 “p/q 都 < root” 写成 “p<root || q<root”（应为 &&），导致递归方向错误；
- 混淆 “节点值” 和 “节点引用”：直接比较
root == p而非root.val == p.val（题目中 p/q 是节点对象，需比较值）；- 漏考虑 “root 是 p/q” 的场景：仅判断 “p/q 分属左右”，导致根节点为目标节点时返回错误。
3. 通用易错点
- 对 LCA 定义的误解：忽略 “节点可作为自身的后代”，这是两道题的核心定义前提；
- 递归栈溢出风险：斜树场景下 h=n，递归深度过大，可改用迭代版优化（236 迭代版需记录父节点，235 迭代版更简单）。
五、深度总结
LCA 问题的解题本质是 “利用树的结构 / 特性，最小化遍历范围”：
- 普通二叉树无特殊特性，只能通过 “后序遍历 + 信号传递” 验证子树存在性，是 “无特性时的通用解法”；
- BST 的有序性提供了 “数值预判” 的可能，将遍历范围从整棵树缩减到单条路径，是 “数据结构特性驱动算法优化” 的典型案例；
- 面试中，这两道题常作为 “递进式提问”：先问 235（BST），再追问 236（普通二叉树），核心考察 “是否能利用数据结构特性简化算法”“是否理解递归的信号传递逻辑”。
天气：🌧️
