Java二叉树: Finding the node that reaches two nodes with shortest distance

Question

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

我已将此任务分解为两个方法，一个名为 canReach，用于在树中搜索节点，另一个方法使用 canReach 的 boolean 返回来确定沿树向下移动以及朝哪个方向移动，名为reachBoth。

通过调试，我非常有信心 canReach 能够准确地搜索树。然而，似乎我永远不会从reachBoth中得到任何答案，除了null(如果两个节点都不存在于树中或根(如果存在的话))，而不是介于两者之间的任何答案。

在树中导航时重复检查对两个节点的访问是一个好主意吗？如果有人能看到我的方法reachBoth 哪里有问题，我将不胜感激。

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