程序员面试攻略　4.5 面试例题：最低公共祖先

4.5 面试例题：最低公共祖先
已知二元搜索树上两个结点的值，请找出它们的公共祖先。你可以假设这两个值肯定存在。这个函数的调用接口如下所示：
int FindLowestCommonAncestor(node *root, int value1, int value2);

算法1：
从两个给定结点的结点出发进行回溯，两条回溯路线的交点就是我们要找的东西。这个算法的具体实现办法是：先用这两个结点的全体祖先分别生成两个链表，再把这两个链表第一次出现不同结点的位置找出来，则它们的前一个结点就是我们要找的东西。

算法2：
从根结点出发，沿着两个结定结点的公共祖先前进。当这两个结点的值同时小于当前结点的值时，沿左指针前进；当这两个结点的值同时大于当前结点的值时，沿右指针前进；当第一次遇到当前结点的值介于两个给定的结点值之间的情况时，这个当前结点就是我们要找的最低公共祖先了。

int FindLowestCommonAncestor(node *root, int value1, int value2)
{
 node *curNode = root;
 for (;;) {
  if (curNode->value > value1 && curNode->value > value2)
   curNode = curNode->left;
  else if (curNode->value < value1 && curNode->value < value2)
   curNode = curNode->right;
  else
   return curNode->value;
 }
}