二叉树中最低的共同祖先

Following is my implementation of lowest common ancestor for a Binary Search tree. I have two question:

以下是我对二进制搜索树的最低共同祖先的实现。我有两个问题：

1) The time complexity is O(n) and space complexity is O(n) worse case but O(logn) average case for both time and space if BST is balanced. is that correct? 2) How can i extend my solution to binary trees and not just binary search trees.

1）时间复杂度为O（n），空间复杂度为O（n）更坏的情况，但如果BST平衡，则时间和空间的O（logn）平均情况。那是对的吗？ 2）如何将我的解决方案扩展到二叉树而不仅仅是二叉树搜索树。

Hope to hear from you soon.

希望早日收到你的消息。

//The function findOrQueue is to enqueue all elements upto target node to a queue
public void findOrQueue(Node target, Node top, LLQueue q) {
    int cmp = target.getData().compareTo(top.getData()); 
    if(cmp == 0) {
        q.enqueue(top);
        return ;
    }
    else if (cmp < 0) {
        q.enqueue(top);
        findOrQueue(target, top.getLeftChild(),q);
    }
    else {
        q.enqueue(top);
        findOrQueue(target, top.getRightChild(),q);
   }
}

public Node LCA(Node n1, Node n2) throws QueueEmptyException {
    LLQueue q1 = new LLQueue();
    LLQueue q2 = new LLQueue();
    findOrQueue(n1,getRoot(),q1);
    findOrQueue(n2,getRoot(),q2);
    Node t = null;
    while (!q1.isEmpty() && !q2.isEmpty()) {
        Node t1 = (Node)q1.dequeue();
        Node t2 = (Node)q2.dequeue();
        if(t1.getData() != t2.getData()) {
            return t;
        }
        else t = t1;
    }
    if(q1.isEmpty() && q2.isEmpty()) 
        return null;
    else
        return t;
    }

1 个解决方案

#1

The key to extending your solution to a general binary tree seems to lie in finding the path connecting the root and a target node. Once obtaining this path, you could easily modify your LCA function to find the lowest common ancestor.

将解决方案扩展到通用二叉树树的关键似乎在于找到连接根节点和目标节点的路径。获得此路径后，您可以轻松修改LCA功能以找到最低共同祖先。

The following crude implementation makes use of LinkedBlockingQueue in package java.util.concurrent.* and Stack in java.util.* - however, any other ordinary queue and stack would also do the trick. The code assumes that the target nodes exists in the tree.

下面的粗略实现使用java.util.concurrent。*中的LinkedBlockingQueue和java.util。*中的Stack - 但是，任何其他普通队列和堆栈也可以使用。该代码假定目标节点存在于树中。

public static void findPath2(Node target,Node top, Stack<Node> path){
    LinkedBlockingQueue<Node> q1 = new LinkedBlockingQueue<Node>(), q2 = new LinkedBlockingQueue<Node>(),
    q3 = new LinkedBlockingQueue<Node>();
    Node n = top;
    Node parrent = null;
    while(n.getData().compareTo(target.getData())!= 0){
        parrent = n;
        if(n.right != null){
            q2.add(n.right);
            q3.add(parrent);
        }
        if(n.left != null){
            q2.add(n.left); 
            q3.add(parrent);
        }
        n = q2.remove();
        q1.add(n);
    }

    Stack<Node> s3 = new Stack<Node>(), s2 = new Stack<Node>();
    while(!q3.isEmpty()){
        s3.push(q3.remove());           
    }       
    for(int i = 1; i <= q2.size(); i++)
        s3.pop();       
    while(!s3.isEmpty())
        s2.push(s3.pop());
    while(!q1.isEmpty())
        s3.push(q1.remove());
    LinkedBlockingQueue<Node> temp = new LinkedBlockingQueue<Node>();
    while(!s2.isEmpty())
        temp.add(s2.pop());
    while(!temp.isEmpty())
        s2.push(temp.remove());
    path.push(s3.pop());
    path.push(s2.pop());
    while(!s3.isEmpty()){
        n = s3.peek();          
        while(n.getData().compareTo(path.peek().getData()) != 0 && !s3.isEmpty()){
            s3.pop();
            s2.pop();
            if(!s3.isEmpty())
                n = s3.peek();
        }
        if(!s3.isEmpty()){
            s3.pop();
            path.push(s2.pop());
        }
    }       
}