chlclan

已知二元搜索树上两个节点的值，请找出他们最低的公共祖先。可以假设两个值肯定存在

 

根据二元搜索树的特性，这里有个隐含的条件：

    除了最低公共祖先之外，其他所有节点要不都是大于该两个节点，要不就是都是小于该两个节点值

 

算法：

检查当前节点

如果value1&value2同时小于当前节点的值

    前进到当前节点的左节点

如果value1&value2同时大于当前节点的值

    前进到当前节点的有节点

否则

    当前节点就是我们要找到的最低公共祖先

   

 

int FindLowestCommonAncestor(node *root, int value1, int value2)

{

    node *CurNode = root;

   

    while(1){

        /*Go to the left child*/

        if(CurNode->value > value1 && CurNode->value > value2)

            CurNode = CurNode->left;

       

        /*Go to the right child*/

        else if(CurNode->valuef < value1 && CurNode->value < value2)

            CurNode = CurNode->right;

       

        /*Else you found the correct node */

        else

            return CurNode->value;

    }

}