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

Question

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

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

通过调试，我非常有信心 canReach 可以准确地搜索树。然而，似乎我永远不会从 reachesBoth 中得到任何答案，除了 null 如果两个节点都不存在于树中，或者如果它们存在于根中，那么它们之间没有任何东西。

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

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

在检查左右子项时将递归更改为 return：

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

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

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

Java Binary Trees: Finding the node that reaches two nodes with shortest distance

java

distance

binary-search-tree

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

Java Binary Trees: Finding the node that reaches two nodes with shortest distance

java

distance

binary-search-tree

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