第19题 在二叉查找树中找到两个结点的最低公共祖先 Lowest Common Ancestor

本文来自《 programming interviews exposed》一书

题目：

Given the value of two nodes in a binary search tree, find the lowest common ancestor. You may assume that both values already exist in the tree.

The function prototype is as follows:

int findLowestCommonAncestor(node* root, int value 1, int value2);

20

/ \

8 22

/ \

4 12

/ \

10 14

比如在上面这个二叉搜索树中，要找4和14的lowest common ancestor, 就应该是8.

算法描述：

因为根节点是所有节点的祖先，又因为二叉树自身的性质，我们会得到，当两个目标节点都比当前节点小的时候，我们走左节点，当两个目标节点都比当前节点大的时候，我们走右节点。第一个碰到的节点的值在两个目标节点之间的节点就是 lowest common ancestor

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->value < value1 && curNode->value < value2)
              curNode = curNode->right;
         else
              return curNode->value;
    }
}

算法的时间复杂度是O(logn)