Javaバイナリツリー：最短距離の2つのノードに到達するノードを見つける

Question

現在、最短距離の2つのノードに到達するノードのJavaのバイナリツリーを検索する方法を書いています。私の考えは、両方のノードがツリーに存在する場合、ルートは両方に到達できる最初のノードになるということです。だから私は再帰し、彼らの両方に到達できるかどうかを確認するためにルートの左/右を確認します。少なくとも1つのノードを見つけた後で両方に到達できない最初のノードを見つけることによって、私は探しているノードから最短距離のノードを持つべきです。

私はこのタスクをツリーのノードを検索するcanReachという名前のメソッドとcanReReachのブール型の戻り値を使ってツリーを下りる方向を指定して、reachBothという名前の方向を決定するという2つのメソッドに分割しました。

デバッグから私はcanReachが正確にツリーを検索していると確信しています。しかし、ツリーの中に両方のノードが存在しない場合はnullを除いて、またルートが存在していなければ、それらの間には何も存在しません。

ツリーをナビゲートしている間、両方のノードへのアクセスを繰り返しチェックしていることをお勧めしますか？私の方法がどこに届くのか誰にでも見えるようにすれば、私は洞察力に感謝するでしょう。

public boolean canReach(T d) { 
     // Helper method for reachesBoth. Takes an argument of data of a Node 
     int comp = d.compareTo(data); // Compare data to current node 
     if (comp == 0) return true; // Found the node 
     if (comp < 0) { // search left for the node 
      if (left != null) { 
       if (left.canReach(d) == true) return true; 
      } 
      return false; 
     } 
     if (comp > 0) { // search right for the node 
      if (right != null) { 
       if (right.canReach(d) == true) return true; 
      } 
      return false; 
     } 
     return false; // Cannot find the node in our tree 
    } 

    public T reachesBoth(T a, T b) { 
     if (canReach(a) == true && canReach(b) == true) { 
      // Found the first node that can reach both desired nodes. 
      // Must continue to see if a node with shorter distance 
      // can reach both nodes as well. 
      if (left != null && right != null) { 
       // Case 1: Two more branches to check 
       if (left.reachesBoth(a, b) != null) left.reachesBoth(a, b); 
       if (right.reachesBoth(a, b) != null) right.reachesBoth(a, b); 
       //Both branches cannot reach both nodes sooner than we can. 
       if (left.reachesBoth(a, b) == null & right.reachesBoth(a, b) == null) { 
        return this.data; 
       } 
      } 
      if (left != null && right == null) { 
       // Case 2: Only left branch to check 
       if (left.reachesBoth(a, b) == null) return this.data; 
      } 
      if (left == null && right != null) { 
       // Case 3: Only right branch to check 
       if (right.reachesBoth(a, b) == null) return this.data; 
      } 
      // Case 4: No more tree to search for a better solution 
      if (left == null && right == null) return this.data; 

     } 

     return null; // Cannot locate both nodes in our tree from our start 
    } 

Answer 1

それは左と右の子供たちをチェックしたときに返すために、あなたの再帰を変更

：トリックをした

if (left.reachesBoth(a, b) != null) return left.reachesBoth(a, b);

if (right.reachesBoth(a, b) != null) return right.reachesBoth(a, b);