題目：求兩個節(jié)點的最近公共祖先 LCA（Latest Common Acestor）
輸入為兩個節(jié)點：a,b。

Situation :BST

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

Situation :Common BT + store parent

基本思想：分別從給定的兩個節(jié)點出發(fā)上溯到根節(jié)點，形成兩條相交的鏈表，問題轉(zhuǎn)化為求這兩個相交鏈表的第一個交點，即傳統(tǒng)方法：求出linkedList A的長度lengthA， linkedList B的長度LengthB。然后讓長的那個鏈表走過abs(lengthA-lengthB)步之后，齊頭并進，就能解決了。

Situation: Common BT

三種常見的做法：對于簡單的模擬題——直接模擬就好了；對于大題目中的求最近公共祖先的小橋段——用tarjan來求，因為好打不容易錯；對于特意考察最近公共祖先，并且數(shù)據(jù)范圍比較大的時候——用在線算法倍增算法，省空間還是硬道理。

深搜+壓棧

深度優(yōu)先遍歷得到兩個序列（數(shù)組），取數(shù)組最前面的公共部分的最后一個元素就是最近公共祖先。

數(shù)組優(yōu)化為棧型隊列，后遍歷到的元素在棧的上面，這樣方便找到第一個公共元素。（將本來的找最后一個公共元素變成找第一個公共元素 。）

想法二：先將樹轉(zhuǎn)為雙向鏈表，代價可能比較大

教科書答案：樹上（一次向上跳2^i個點）倍增求LCA