首先我们先回顾下什么叫LCA

LCA：树上两个点之间距离最近的公共祖先

在ACM比赛中常常是出现LCA的题目，而求LCA也有很多种方法。一般分为两大类，在线和离线（不懂什么叫在线和离线的你们自己去百度）

---

我在这篇文章中给你们介绍的方法是-倍增法（在线求LCA的一种方法）

如下图所示

这是一颗非常常见的二叉树，树上的每个节点都保存着两个信息-树节点的编号和树节点的深度。

![I_G]D5SBKT)7S`]5PFV)}XT.png](https://img.haomeiwen.com/i1250148/ed8fc2beebffccf5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

对于这样的一棵树，我们可以很直观的提出一种求LCA算法，对于同一颗树上的两个不同节点，比如上图所示的8节点和5节点，我们 先让深度为3的8节点上升到他的父节点-深度为2的4节点上，然后4节点和5节点不停的向他们的父节点移动，直到他们的父节点相同，8与5的最近公共祖先就求出来了 。

我们来总结下上面的算法流程

• 1 先让树节点深度大的到达树节点深度的小的深度
• 2 两个树节点同时向他们的父节点移动
• 3 如果两个树节点到达的父节点相同，则LCA求出来了

上面算法对于求一对节点的LCA的时间复杂度是o(n)。对于N对算法复杂度自然就是0（n^2)。

那么,我们有没有办法来优化这个算法的时间复杂度呢，有，当然是有了！

---

ok!终于要轮到我们的主角二进制闪亮登场了！ZZZ。

二进制：这个我就不用介绍了吧。

我们该怎么利用二进制来优化呢？我们都知道自然数都是能够用二进制表示的，例如17 的二进制表示为10001，我们在想想我们刚才的那个总结的那个算法。有没有有一丝灵感迸发呢？ZZZ

---

对于算法中第一步，两个节点的深度之差我们是能够计算的出来的，假设节点的深度之差是17，那么我们这个时候只需要两个步骤，第一个步骤，向上移动16，

第二个步骤，向上移动一位，。有没有明白什么呢？

对于算法中的第二步，虽然我们不知道离他们最近的祖先的节点的深度的是多少，但是我们可以知道一点，那就是这个树的根一定是这两个节点的祖先，OK，那么我就就可以逆向思维来求，求出两个节点的最多向上移动多少步，仍然没到达最近的公共祖先。