java - 二叉树中的最低公共(public)祖先

Question

以下是我对二叉搜索树的最低公共(public)祖先的实现。我有两个问题:

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

希望尽快收到您的来信。

//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;
    }

Answer 1

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

下面的粗略实现利用了 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());
        }
    }       
}