1

只是想知道以下算法在二叉搜索树中找到两个节点的最低共同祖先的效率如何。

Node getLowestCommonAncestor (Node root, Node a, Node b) {

   Find the in-order traversal of Node root.
   Find temp1 = the in-order successor of Node a.
   Find temp2 = the in-order successor of Node b.

   return min (temp1, temp2);
}
4

3 回答 3

8

Searching for the lowest common ancestor in a binary search tree is simpler than that: observe that the LCA is the node where the searches for item A and item B diverge for the first time.

Start from the root, and search for A and B at the same time. As long as both searches take you in the same direction, continue the search. Once you arrive at the node such that searching for A and B take you to different subtrees, you know that the current node is the LCA.

于 2012-09-23T12:23:20.803 回答
2

A node at the bottom of a large binary search trees can have an in-order successor close to it, for instance if it is the left child of a node, its in-order successor is its parent.

Two nodes descending from different children of the root will have the root as their least common ancestor, no matter where they are, so I believe that your algorithm gets this case wrong.

This is a discussion of efficient LCA algorithms (given time to build a preparatory data structure) at http://en.wikipedia.org/wiki/Lowest_common_ancestor, with pointers to code.

An inefficient but simple way of finding the LCA is as follows: in the tree keep pointers from children to parents and a note of the depth of each node. Given two nodes, move up from the deepest one until the depth if the same. If you are pointing at the other node, it is the LCA. Otherwise move up one step from each node and check again, and so on, until you meet at the LCA.

于 2012-09-23T12:24:58.850 回答
0

找到 BST 的 LCA 是直接的：

找到node1和node2存在于不同侧的节点。但如果node1是node2 比的祖先，我们也将不得不返回node1。下面的代码实现了这个算法。

TreeNode<K> commonAncestor(TreeNode t, K k1, K k2){
        if(t==null) return null;
        while(true)
        {
           int c1=t.k.compareTo(k1);
           int c2=t.k.compareTo(k2);
           if(c1*c2<=0)
           {
               return t;
           }
           else
           {
               if(c1<0)
               {
                   t = t.right;
               }
               else
               {
                   t = t.left;
               }
           }
        }
    }
于 2013-10-06T19:33:41.820 回答