Java Binary Trees: Den Knoten finden, der zwei Knoten mit der kürzesten Entfernung erreicht

Question

Ich schreibe gerade eine Methode, die einen binären Baum in Java nach dem Knoten durchsucht, der zwei Knoten in der kürzesten Entfernung erreicht. Meine Idee ist, dass, wenn beide Knoten in der Struktur vorhanden sind, die Wurzel der erste Knoten sein würde, der beides erreichen kann. Also rekrutiere ich und überprüfe die Links/Rechts von der Wurzel, um zu sehen, ob sie beide auch erreichen können. Indem ich den ersten Knoten finde, der beide nicht erreichen kann, nachdem ich mindestens einen Knoten gefunden habe, sollte der Knoten mit dem kürzesten Abstand von den beiden, nach denen ich suche, vorliegen.

Ich habe diese Aufgabe auf zwei Methoden aufgeteilt, eine namens CanReach, die den Baum nach einem Knoten durchsucht und eine andere, die die boolean Rückgabe von canReach verwendet, um zu bestimmen, wie man in der Baumstruktur und in welcher Richtung mit dem Namen reachBoth weitergeht.

Durch Debugging bin ich ziemlich zuversichtlich, dass CanReach den Baum genau sucht. Es scheint jedoch, dass ich niemals mit einer Antwort außerhalb von lowsboth komme, außer null, wenn beide Knoten nicht in der Struktur oder der Wurzel vorhanden sind, wenn sie sind, niemals dazwischen.

Wird beim Navigieren im Baum immer wieder nach dem Zugriff auf beide Knoten gesucht? Wenn irgendjemand sehen kann, wo meine Methode erreicht, ist beides abgehört, würde ich die Einsicht schätzen.

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

ändern Rekursion zurückzukehren, wenn sie die linken und rechten Kinder prüft:

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

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