定义
给定一棵有根树,若结点 z 既是结点 x 的祖先,也是结点 y 的祖先,则称 z 是x,y的公共祖先。
在 x,y 的所有公共祖先中,深度最大的一个称为 x,y 的最近公共祖先,记为LCA(x,y)。
LCA(4 , 7) = 2,LCA(6,7) = 5
实现
暴力大法好
若求LCA(4 , 7),分别求 4 和 7 到根节点的路径。
4 -> root 的路径为:4 -> 2 -> 1。
7 -> root 的路径为:7 -> 5 -> 2 -> 1。
那么在两个路径*有的第一个点即为答案。
所以LCA(4 , 7) = 2。
暴力大法比较简单也不怎么常用,不过多介绍。
Tarjan
ST