Java二叉树：找到达到两个节点的距离最短的节点

Question

我目前正在编写一个方法，在Java中搜索以最短距离到达两个节点​​的节点。我的想法是，如果树中都存在两个节点，则根将是第一个可以同时到达的节点。所以我递归并检查根的左边/右边，看看它们是否也能达到两者。通过找到至少找到一个节点后找不到的第一个节点，我应该找到距离我所搜索的节点最近的节点。

我已经将此任务分解为两个方法，一个名为canReach，它搜索树中的一个节点，另一个使用canReach的布尔返回来确定向下移动树，并沿着什么方向命名为reachingBoth。

通过调试我非常有信心canReach准确地搜索树。然而，如果两个节点都不存在于树中，或者如果它们是根，那么从来没有任何介于两者之间的东西。

重复检查两个节点的访问，同时向下导航树是一个好主意？如果任何人都可以看到我的方法到达哪里都有问题，我会很感激这种洞察力。

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