二叉搜索树的最低共同祖先代码不被接受

Question

Q:给定一个二叉搜索树(BST)，在BST中找出两个给定节点的最低共同祖先(LCA)。

根据维基百科上LCA的定义:"最低共同祖先被定义在两个节点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 86５ ７4之前

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

Answer 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;
    }  
    while(max<root.val) {
        root=root.left;
    }    
    while (min>root.val) {
        root=root.right;
    }      
    return root;
}
}