最近公共祖先（Lowest Common Ancestor，LCA）是有根树中同时作为两个节点祖先、并且距离这两个节点最近的节点。它也可以理解为同时包含两个目标节点的最小子树的根节点。若其中一个目标本身就是另一个目标的祖先，通常将这个目标自身视为最近公共祖先。MIT 的算法课程材料采用了“包含两个目标的最小子树之根”这一描述。
递归汇总
对于普通二叉树，可以从根节点开始递归搜索两个目标：
- 分别搜索当前节点的左子树和右子树。
- 搜索结果表示当前子树内发现的有效节点：没有找到时返回空；只找到一个目标时返回该目标；已经确定公共祖先时返回该祖先。
- 如果左右子树都返回非空结果，说明两个目标分别从两侧汇合，当前节点就是最近公共祖先。
- 如果只有一侧返回非空结果，则把这一结果继续向上返回。
- 如果当前节点本身就是一个目标，则当前节点也作为有效结果向上返回。
这个过程可以概括为：递归向下寻找，返回值向上汇总；第一个同时收到左右两侧有效结果的节点，就是最近公共祖先。
在两个目标都存在的前提下，这种方法最多访问每个节点一次，时间复杂度为 O(n)，递归调用栈的空间复杂度为 O(h)，其中 h 是树高。若不能保证两个目标都存在，还需要额外记录找到的目标数量，否则结果可能只是唯一存在的目标。
父节点表
可以使用栈或队列迭代遍历树，同时记录每个节点的父节点。找到两个目标后，先把一个目标及其所有祖先放入集合，再从另一个目标沿父节点向上移动；遇到的第一个已在集合中的节点就是最近公共祖先。
这种方法不依赖节点值的大小关系，时间复杂度为 O(n)，父节点表和祖先集合需要 O(n) 额外空间。
比较根路径
也可以分别找到从根节点到两个目标的路径，再从路径起点依次比较。两条路径最后一个相同的节点就是最近公共祖先。
这种方法把问题转换为寻找两条路径的最后一个公共位置。单次查询通常需要 O(n) 时间；路径长度最多为 h，寻找路径时还需要相应的遍历空间。
使用节点的父指针
如果节点本身保存父节点指针，可以直接从两个目标向上寻找，不必重新遍历整棵树。先计算两个节点的深度，将较深者提升到相同深度，然后让两者同时向上移动，第一次相遇的位置就是最近公共祖先。
这种方法需要 O(h) 时间，并且可以只使用 O(1) 额外空间。它依赖节点能够访问父节点，不适用于只保存子节点引用的结构。
利用二叉搜索树的有序性
在二叉搜索树中，可以利用键值顺序缩小搜索范围：
- 两个目标值都小于当前节点值时，继续搜索左子树。
- 两个目标值都大于当前节点值时，继续搜索右子树。
- 两个目标分居两侧，或者当前节点就是其中一个目标时，当前节点就是最近公共祖先。
该过程可以迭代完成，时间复杂度为 O(h)，额外空间为 O(1)。它只适用于满足搜索树键值约束的树，不能直接用于普通二叉树。
大量查询的预处理方法
如果同一棵静态树需要回答大量查询，可以先预处理树，再降低每次查询的成本。MIT 的高级数据结构课程材料介绍了 LCA、欧拉序列与区间最小值查询之间的关系，以及祖先跳跃指针等预处理思想。
常见方法包括：
- 倍增法：为每个节点保存第 1、2、4、8 等距离的祖先。通常使用 O(n log n) 时间和空间预处理，每次查询为 O(log n)。
- 欧拉序列与 RMQ：记录遍历序列及节点深度，把 LCA 转换为区间最小值查询。根据 RMQ 结构不同，可以在预处理与查询时间之间取舍；高级实现可达到 O(n) 空间和 O(1) 查询。
- Tarjan 离线算法：预先取得全部查询，结合后序处理和并查集一次性回答。MIT 的高级算法习题材料给出的复杂度为 O((n + m)α(n))，其中 m 是查询数量。
单次查询通常选择递归汇总或父节点表；二叉搜索树适合利用有序性；同一棵树上的大量查询则更适合预处理方法。