最近公共祖先 (lowest common ancestor) 是一个有根树中，两个节点深度最大的共同祖先。

定义

设 T = (V, E) 是一棵有根树，A \subset V 是一个顶点集。若对任意 u \in A，a 是 u 的祖先，则称 a 是 A 中节点的公共祖先；在所有的公共祖先中，深度最大的节点称为最近公共祖先（lowest common ancestor），记为 \mathrm{LCA}(A)。

通常我们更多讨论两个节点 u, v 的 LCA，记为 \mathrm{LCA}(u, v)。

以上定义中，我们特别地规定 u 也是自身的祖先。以下讨论也遵循这一规定。

性质

基本性质

u 是 v 的祖先，等价于 u = \mathrm{LCA}(u, v)。

若 u, v 位于某节点 w 的两棵不同子树上，则 w = \operatorname{LCA}(u, v)。

最短路

树上两点 u, v 的唯一最短路径一定经过 \mathrm{LCA}(u, v)。此时，两点的距离（最短路径长度）

其中 h(u) 代表 u 的深度。