最近公共祖先

最近公共祖先是指在一棵有根树中，两个节点向根节点路径上的第一个交汇点。求解LCA问题，本质上是高效地找到树中任意两个节点的这个最深公共祖先。

暴力求解法需要沿着父指针回溯并比较路径，但效率低下。为此，我们采用倍增等算法进行优化。该算法通过预处理，让每个节点存储其向上第1、2、4...级的祖先信息。在查询时，我们先将两个节点调整到同一深度，然后利用二进制拼凑的思想，让它们一同跳跃式地向上寻找，直到找到LCA。

高效求解LCA的意义重大，它能够将树上两点之间的路径问题转化为与LCA相关的问题，是解决树上最短路径、节点关系等众多高级问题的基础组件。

【思维导图】

【题目知识点分类】