问题:给定一个二叉搜索树 (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 循环有什么不同吗?谢谢!
最佳答案
原因是第一次尝试只在左转完成后才右转,这意味着任何右转左转的目标节点都无法到达。
例如:
3 2 8 6 5 7 4
在上面的树中,4和7的最低共同祖先是6,但无法到达。
关于java - 不接受二进制搜索树代码的最低公共(public)祖先,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40008229/