題目：求兩個節(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
