浅析LCA

· · 个人记录

一、LCA的定义

  1. 公共祖先：在一棵树中，若结点z既是结点x的祖先，又是结点y的祖先，则称结点z为结点x和y的公共祖先。

  2. 最近公共祖先：在x，y的公共祖先中，深度最大的一个结点，称为x，y的最近公共祖先（LCA）。PS:自己可以是自己的祖先。

    下图中的树，LCA(4,5)=2，LCA(1,3)=1。（1也算1的祖先）

    二 、LCA的用途

    1. ...

      三、LCA的求法

    2. 树上倍增求LCA