题目：求两个节点的最近公共祖先 LCA（Latest Common Acestor）
输入为两个节点：a,b。

Situation :BST

对于BST， ancestor.value > a.value && ancestor.value < b.value。

Situation :Common BT + store parent

基本思想：分别从给定的两个节点出发上溯到根节点，形成两条相交的链表，问题转化为求这两个相交链表的第一个交点，即传统方法：求出linkedList A的长度lengthA， linkedList B的长度LengthB。然后让长的那个链表走过abs(lengthA-lengthB)步之后，齐头并进，就能解决了。

Situation: Common BT

三种常见的做法：对于简单的模拟题——直接模拟就好了；对于大题目中的求最近公共祖先的小桥段——用tarjan来求，因为好打不容易错；对于特意考察最近公共祖先，并且数据范围比较大的时候——用在线算法倍增算法，省空间还是硬道理。

深搜+压栈

深度优先遍历得到两个序列（数组），取数组最前面的公共部分的最后一个元素就是最近公共祖先。

数组优化为栈型队列，后遍历到的元素在栈的上面，这样方便找到第一个公共元素。（将本来的找最后一个公共元素变成找第一个公共元素 。）

想法二：先将树转为双向链表，代价可能比较大

教科书答案：树上（一次向上跳2^i个点）倍增求LCA