java - 不接受二进制搜索树代码的最低公共(public)祖先

Question

问题:给定一个二叉搜索树 (BST)，找到 BST 中两个给定节点的最低公共(public)祖先 (LCA)。

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

---

我试着写了两种方法来解决这个问题。第二个被接受了，但是我不明白为什么第一个是错误的。

代码如下:

1:

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    while(max<root.val) {
        root=root.left;
    }    
    while (min>root.val) {
        root=root.right;
    }      
    return root;
}
}

2:

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    int max = Math.max(p.val, q.val);
    int min = Math.min(p.val, q.val);
    while (max<root.val||min>root.val) {
         root=root.val<min?root.right:root.left;
    }      
    return root;
}
}

如果我拆分 while 循环有什么不同吗？谢谢!

Answer 1

原因是第一次尝试只在左转完成后才右转，这意味着任何右转左转的目标节点都无法到达。

例如:

      3 2         8         6        5 7       4

在上面的树中，4和7的最低共同祖先是6，但无法到达。