二叉树中的最近公共祖先

Question

以下是我对二叉搜索树最近公共祖先的实现。我有两个问题：

1) 如果BST是平衡的，则时间复杂度为O（logn），空间复杂度为O（logn）的平均情况，但在最坏情况下时间复杂度为O（n），空间复杂度为O（n）。这样正确吗？

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

- ueg1990

---

为什么这个算法不能在普通二叉树上运行？我没有看到任何强制规定特定节点顺序的条件。 - jma127

函数findOrQueue是为二叉搜索树而不是二叉树定义的。 - ueg1990

为什么在 findOrQueue() 中要使用比较？简单遍历树即可。 - jma127

我没有父指针，所以我必须先找到节点。 - ueg1990

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());
        }
    }       
}

- Tuan-Tran