二叉树中最低的共同祖先 [英] Lowest Common Ancestor in a Binary tree

问题描述

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

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

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

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.

希望尽快收到您的回复。

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

推荐答案

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

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.

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

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.

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

这篇关于二叉树中最低的共同祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！