java - 查找最低命令祖先在树搜索中失败(不是算法问题，而是 Java 问题)

Question

非常简单的树问题，不知何故结果为空(应该是1，因为1是2和3的父节点)，找不到原因。该方法本身已通过Leetcode在线判断。

这是问题的链接:

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

给定一棵二叉树，找到树中两个给定节点的最低公共(public)祖先(LCA)。

根据维基百科上 LCA 的定义:“最低共同祖先被定义为两个节点 v 和 w 之间作为 T 中同时具有 v 和 w 作为后代的最低节点(其中我们允许一个节点是本身)。”

public class LowestCommonAncestor2 {

    public static TreeNode mockTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left = node2;
        node1.right = node3;
        return node1;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode t1, TreeNode t2) {
           if (root == null || root == t1 || root == t2) {
               return root;
           }

           TreeNode left = lowestCommonAncestor(root.left, t1, t2);
           TreeNode right = lowestCommonAncestor(root.right, t1, t2);

           if (left != null && right != null) 
               return root;
           if (left != null) 
               return left;
           if (right != null) 
               return right;
           return null;
    }

    public static void main (String [] args) {
        LowestCommonAncestor2 test = new LowestCommonAncestor2();
        TreeNode root = mockTree();
        TreeNode target1 = new TreeNode(2);
        TreeNode target2 = new TreeNode(3);
        TreeNode result = test.lowestCommonAncestor(root, target1, target2);
        System.out.println(result);
    } 
}

和TreeNode定义如下:

public class TreeNode {
     public int val;
     public TreeNode left, right;
     public TreeNode(int val) {
         this.val = val;
         this.left = this.right = null;
     }
}

Answer 1

由于这行代码而发生错误

if (root == null || root == t1 || root == t2) 

仔细思考执行此方法时要比较的内容

TreeNode result = test.lowestCommonAncestor(root, target1, target2);

当您调用 LCA 方法时，第一个 if 语句中的所有条件都不会计算为 true，因为没有一个语句为 true，这是正确的。但是，现在让我们开始第一个递归调用，

TreeNode left = lowestCommonAncestor(root.left, t1, t2);
TreeNode right = lowestCommonAncestor(root.right, t1, t2);

对于 lowestCommonAncestor(root.left, t1, t2)，请仔细考虑第一个 if 语句。在这种情况下，root 现在是 node2，而 t1 和 t2 仍然是在主要像以前一样。但是等等，这就是问题发生的原因。您可能期望语句 root == t1 的计算结果为 true，但它的计算结果却并非 true，原因如下。 node2 和 target1 是两个不同的对象，Java 的 == 运算符并不执行您认为的操作。使用 == 运算符比较对象时，比较的是对象的地址而不是对象的实际内容。因此，由于 node2 和 target1 在程序中占用不同的数据空间，因此它们没有相同的地址。您将看到 == 运算符更常用于比较 Java 中的基本类型(例如 int 和 char)，因为它与比较对象不同。这就是为什么您会看到 Java 中使用 .equals 方法来比较字符串，因为字符串是对象。

那么解决方案是什么？

在 TreeNode 类中创建一个 equals 方法，该方法返回 boolean 值并接受另一个 TreeNode 对象作为参数。另外，请确保该方法是实例方法而不是静态方法，以便该方法在代码中的执行如下所示，

public boolean equals(TreeNode node){ //method address
    //rest of the method has to be implemented yourself
    //ask yourself, how are two treenodes considered equal in your situation?
}

最后，将 root == t1 替换为

root.equals(t1)

和root == t2与

root.equals(t2)