首先我们先回顾下什么叫LCA
LCA：树上两个点之间距离最近的公共祖先
在ACM比赛中常常是出现LCA的题目，而求LCA也有很多种方法。一般分为两大类，在线和离线（不懂什么叫在线和离线的你们自己去百度）
我在这篇文章中给你们介绍的方法是-倍增法（在线求LCA的一种方法）
如下图所示
这是一颗非常常见的二叉树，树上的每个节点都保存着两个信息-树节点的编号和树节点的深度。
![I_G]D5SBKT)7S`]5PFV)}XT.png](http://upload-images.jianshu.io/upload_images/1250148-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，
第二个步骤，向上移动一位，。有没有明白什么呢？
