4.5 面試?yán)}：最低公共祖先
已知二元搜索樹(shù)上兩個(gè)結(jié)點(diǎn)的值，請(qǐng)找出它們的公共祖先。你可以假設(shè)這兩個(gè)值肯定存在。這個(gè)函數(shù)的調(diào)用接口如下所示：
int FindLowestCommonAncestor(node *root, int value1, int value2);

算法1：
從兩個(gè)給定結(jié)點(diǎn)的結(jié)點(diǎn)出發(fā)進(jìn)行回溯，兩條回溯路線的交點(diǎn)就是我們要找的東西。這個(gè)算法的具體實(shí)現(xiàn)辦法是：先用這兩個(gè)結(jié)點(diǎn)的全體祖先分別生成兩個(gè)鏈表，再把這兩個(gè)鏈表第一次出現(xiàn)不同結(jié)點(diǎn)的位置找出來(lái)，則它們的前一個(gè)結(jié)點(diǎn)就是我們要找的東西。

算法2：
從根結(jié)點(diǎn)出發(fā)，沿著兩個(gè)結(jié)定結(jié)點(diǎn)的公共祖先前進(jìn)。當(dāng)這兩個(gè)結(jié)點(diǎn)的值同時(shí)小于當(dāng)前結(jié)點(diǎn)的值時(shí)，沿左指針前進(jìn)；當(dāng)這兩個(gè)結(jié)點(diǎn)的值同時(shí)大于當(dāng)前結(jié)點(diǎn)的值時(shí)，沿右指針前進(jìn)；當(dāng)?shù)谝淮斡龅疆?dāng)前結(jié)點(diǎn)的值介于兩個(gè)給定的結(jié)點(diǎn)值之間的情況時(shí)，這個(gè)當(dāng)前結(jié)點(diǎn)就是我們要找的最低公共祖先了。