バイナリツリー内の最も低い共通祖先

Question

以下は、バイナリ検索ツリーの最も一般的な祖先の実装です。

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の *と java.utilのでスタックにLinkedBlockingQueueを使用しています* - 。しかし、他の通常のキューとスタックはまた、トリックを行うだろう。このコードでは、ターゲットノードがツリー内に存在することを前提としています。

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