最近公共祖先（Lowest Common Ancestor，简称 LCA）是二叉树类题目中非常经典的一类问题。给定一棵二叉树和树中的两个节点 p 和 q，最近公共祖先指的是同时是 p 和 q 的祖先且深度最大的那个节点。注意，一个节点可以算是它自己的祖先。这个问题在 LeetCode 上对应第 236 题，是许多大厂面试的高频考题。解决它的思路并不唯一，最常见的是递归分治法和父节点记录法，两种方法各有特点，下面我们结合代码逐一分析。
什么是最近公共祖先
先用一个具体例子说明。假设有这样一棵二叉树：根节点为 3，它的左子节点是 5，右子节点是 1。节点 5 又有子节点 6 和 2，节点 2 的子节点是 7 和 4；节点 1 的子节点是 0 和 8。如果我们要找节点 7 和节点 4 的最近公共祖先，答案是节点 2，因为 7 和 4 都在以 2 为根的子树里，而 2 是满足条件的最深节点。而如果要找节点 6 和节点 4 的最近公共祖先，答案则是节点 5。
这里有一个容易混淆的点：最近公共祖先不一定是直接父节点，也不一定是 p 或 q 本身。但如果 p 恰好是 q 的祖先，那么答案就是 p。理解了这个定义，后面的解法就好推导了。
方法一：递归分治法
递归分治是解决这道题最优雅的方案。整体思路是：对当前节点调用一个查找函数，在以当前节点为根的子树中寻找 p 和 q。如果在左右子树中分别找到了其中一个节点，说明当前节点就是分岔点，也就是最近公共祖先；如果只有一侧找到了结果，就把那一侧的结果向上返回。
递归函数的定义非常关键：lowestCommonAncestor(root, p, q) 表示在以 root 为根的子树中寻找 p 和 q 的最近公共祖先。递归终止条件是 root 为空，或者 root 就是 p 或 q，此时直接返回 root。递归过程中，先在左子树查找得到 left，再在右子树查找得到 right，然后分三种情况讨论：left 和 right 都不为空，说明 p 和 q 分布在 root 两侧，root 就是答案；只有 left 不为空，说明两个节点都在左子树，返回 left；只有 right 不为空，同理返回 right。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def lowestCommonAncestor(self, root, p, q):
# 递归终止条件：遇到空节点，或者遇到 p 或 q 本身
if root is None or root == p or root == q:
return root
# 分别在左右子树中查找
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
# 左右子树各找到一个，当前节点就是最近公共祖先
if left and right:
return root
# 都在左子树，返回左子树的结果
if left:
return left
# 都在右子树，返回右子树的结果
return right这段代码的精妙之处在于它处理了所有边界情况。当 root 等于 p 或 q 时直接返回，这隐含了一个假设：如果 q 在 p 的子树中，查找过程中会先遇到 p 并返回，最终答案就是 p，这正好符合一个节点可以是自己祖先的定义。时间复杂度方面，每个节点最多被访问一次，所以是 O(n)，其中 n 是树中节点总数。空间复杂度取决于递归栈的深度，最坏情况下（树退化成链表）为 O(n)，平衡时为 O(log n)。
方法二：父节点记录法
第二种思路更加直观：先用一次遍历（DFS 或 BFS 均可）把每个节点的父节点记录到哈希表中，然后从节点 p 开始不断向上回溯，把沿途经过的所有祖先（包括 p 自己）存入一个集合。接着从 q 出发向上回溯，第一个出现在这个集合中的节点，就是 p 和 q 的最近公共祖先。
这个方法相当于把树的问题转化成了两条链表求交点的问题。虽然思路朴素，但它的扩展性很好，尤其适合需要多次查询 LCA 的场景：父节点哈希表只需要构建一次，后续每次查询都只需要回溯路径长度，效率可观。
class Solution:
def lowestCommonAncestor(self, root, p, q):
# 第一步：遍历整棵树，记录每个节点的父节点
parent = {root: None}
stack = [root]
while stack:
node = stack.pop()
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
# 第二步：回溯 p 的所有祖先，存入集合
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
# 第三步：从 q 向上走，第一个出现在集合中的节点就是答案
while q not in ancestors:
q = parent[q]
return q时间复杂度同样是 O(n)，因为要遍历整棵树并回溯路径。空间复杂度方面，除了哈希表和祖先集合占用的 O(n) 空间外，不需要递归栈，这是它相对递归法的一个优势——不存在递归深度过深导致栈溢出的风险。在工程实践中，如果树的规模极大或者节点数据是流式到达的，这种非递归写法往往更稳妥。
进阶：二叉搜索树的优化解法
如果题目给出的树是二叉搜索树（BST），还可以利用节点值的大小关系做进一步优化。对于节点 p 和 q，从根节点开始遍历：如果当前节点的值同时大于 p 和 q 的值，说明两个目标都在左子树，往左走；如果当前节点的值同时小于 p 和 q 的值，说明两个目标都在右子树，往右走；否则当前节点就是分岔点，即最近公共祖先。
class Solution:
def lowestCommonAncestor(self, root, p, q):
node = root
while node:
if node.val > p.val and node.val > q.val:
# 两个节点都在左子树
node = node.left
elif node.val < p.val and node.val < q.val:
# 两个节点都在右子树
node = node.right
else:
# 当前节点处于两值之间（或等于其一），就是答案
return node
return None这个解法不需要递归，也不需要访问全部节点，时间复杂度为 O(h)，h 是树的高度。对于一棵平衡的二叉搜索树，效率是 O(log n)，明显优于通用解法的 O(n)。这也提醒我们，刷题时一定要注意题目给出的附加条件，BST 的有序性质往往能把通用问题简化成更高效的版本。
两种方法对比与选择建议
递归分治法的优势在于代码简洁、不需要额外空间存储父节点关系，是面试中首选的写法，面试官通常也期待你能讲清楚递归函数的定义和三种返回情况的推理过程。父节点记录法的优势在于思路直观、避免递归开销，并且天然适合多次查询的场景，只要预处理一次父节点表，后续查询都很快。
实际选择时可以参考几个维度：如果只是单次查询，递归分治更优雅；如果树规模大且需要频繁查询不同节点对的 LCA，建议用父节点记录法，甚至可以进一步学习 Tarjan 算法或倍增法这类离线与在线的 LCA 专用算法；如果树是二叉搜索树，直接利用值的大小关系走一条路径即可。掌握这几种思路后，再遇到变体题目，比如带父指针的三叉链表节点求 LCA，也能举一反三，用回溯加集合的思路轻松解决。