posts - 63, comments - 37, trackbacks - 0, articles - 0
  IT博客 :: 首页 :: 新随笔 :: 联系 ::  :: 管理

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

 

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

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

 

算法:

检查当前节点

如果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;

    }

}

只有注册用户登录后才能发表评论。