Find Lowest Command Ancestor 在树搜索中失败（不是算法问题，而是 Java 问题）

Question

很简单的树问题，不知为何结果为空（应该是1，因为1是2&3的父节点），找不到原因。方法本身已经通过了Leetcode在线判断

这是问题的 link：

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

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

根据维基百科上LCA的定义：“最低公共祖先定义在两个节点v和w之间，作为T中同时具有v和w作为后代的最低节点（我们允许一个节点是a自己的后代）。”

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

树节点定义如下：

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 语句中的 none 个条件将计算为真，因为 none 个语句为真，这是正确的。但是，现在让我们开始第一个递归调用，

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

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

那有什么办法呢？

在您的 TreeNode class 中创建一个 equals 方法，该方法 returns 是一个布尔值，并将另一个 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)

Answer 2

你可以试试这个：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode t1, TreeNode t2) {
       if((search(root,t1)==null)||(search(root,t2)==null)
           return null;           
       if(search(root.left,t1)!=null)
       {          
           if(search(root.left,t2)!=null)
              return lowestCommonAncestor(root.left,t1,t2);
       }
       else if(search(root.right,t2)!=null)            
           return lowestCommonAncestor(root.right,t1,t2);
       return root;                                   
}

search 方法在树中搜索 TreeNode，我会把它留给你；）。

说明

首先我们检查 root 树是否包含节点 t1 和 t2，如果 root 不包含其中一个我们 return null因为没有祖先。

之后我们在root.left中搜索t1，如果我们找到它我们在root.left中搜索t2，如果我们找到它那么最不共同的祖先必须在 root.left 中，但我们还不能确定它，所以我们递归调用带有 lowestCommonAncestor(root.left,t1,t2) 的方法。

现在，如果我们在右边找到 t2，在右边找到 t1，那么最不常见的祖先在 right 中，我们递归调用。

在所有其他情况下，我们 return root 因为 t1 在左边而 t2 在右边，反之亦然，在这两种情况下 root 都是共同的祖先（因为我们检查）所以它是最不常见的祖先。

如果我们被允许在每个 TreeNode 中有一个 parent 指针，更好的算法是从 t1.parent 开始沿着树向上走，并且只在 p=t1.parent 时停止（或 t1.parent.parent，你明白了）是 t2 的祖先。

Find Lowest Command Ancestor 在树搜索中失败（不是算法问题，而是 Java 问题）

Find Lowest Command Ancestor fail on tree search (Not algorithm issue, but more a Java issue)

java

tree

binary-tree

divide-and-conquer

binary-search-tree

说明