当我尝试让它搜索我的二叉树时，为什么我的“最低共同祖先”函数不断返回 null？

Question

public String LCA(String s, String t) throws IllegalArgumentException {
        // Check if s or t are null or not in the tree
        if (s == null || t == null || !stringsToNodes.containsKey(s) || !stringsToNodes.containsKey(t)) {
            throw new IllegalArgumentException("s or t are null or not in the tree");
        }
    
        // Find nodes containing s and t
        Node nodeS = stringsToNodes.get(s);
        Node nodeT = stringsToNodes.get(t);
    
        // Get paths from nodes to the root
        ArrayStack<Node> pathS = getPathToRoot(nodeS);
        ArrayStack<Node> pathT = getPathToRoot(nodeT);
    
        // Find the intersection of paths
        Node lca = findIntersection(pathS, pathT);
    
        // Return the value of the LCA or null if not found
        return lca != null ? lca.s : null;
    }
    
    // method to find the path from a node to the root
    private ArrayStack<Node> getPathToRoot(Node node) {
        ArrayStack<Node> path = new ArrayStack<>();
        while (node != null) {
            path.add(node);
            node = node.parent;
        }
        return path;
    }
    
  // method to find the intersection of two paths
private Node findIntersection(ArrayStack<Node> pathS, ArrayStack<Node> pathT) {
    Node intersect = null;
    
    // Iterate over both paths until one of them is exhausted
    while (!pathS.isEmpty() && !pathT.isEmpty()) {
        Node nodeS = pathS.get(pathS.size() - 1);
        Node nodeT = pathT.get(pathT.size() - 1);
        if (nodeS == nodeT) {
            intersect = nodeS;
        } else {
            break;
        }
        pathS.remove(pathS.size() - 1); // Move to the previous node in pathS
        pathT.remove(pathT.size() - 1); // Move to the previous node in pathT
    }
    
    return intersect;
}

这是我的职责

我尝试过不使用私有方法来完成此操作，但我无法在网上找到任何其他解决方案。

Answer 1

一个潜在的问题可能是在 findIntersection 方法中使用 == 比较节点。您应该比较它们的值，而不是直接使用 == 来比较节点，而是比较引用。

替换 findIntersection 方法的这一部分：

if (nodeS == nodeT) {
    intersect = nodeS;
}

与：

if (nodeS.equals(nodeT)) {
    intersect = nodeS;
}