w*********2
发帖数: 3 | 1 题目描述：http://www.lintcode.com/en/problem/lowest-common-ancestor/
我用的是top-down策略，即从root向下扫描，如果两个目标点都在左侧或者右侧，则
root移到左节点或者右节点，继续扫描，直到两个目标节点不在同一侧。
小弟不才，在Lintcode上面提交代码始终无法通过，总是在第八个test时fail。实在想
不出来代码问题在哪儿，跪求版上的大牛们指点！附上代码如下：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
if (A == null) {
return B;
} else if (B == null) {
return A;
}
TreeNode node = root;
while (find(node.left, A) && find(node.left, B)) {
node = node.left;
}
while (find(node.right, A) && find(node.right, B)) {
node = node.right;
}
return node;
}
public boolean find(TreeNode root, TreeNode target) {
if (root == null) {
return false;
}
if (root.val == target.val) {
return true;
}
return find(root.left, target) || find(root.right, target);
}
不胜感激！ | z***y
发帖数: 73 | | w*********2
发帖数: 3 | 3 我考虑过这种情况了。
假设A是F的右子节点，B是A的右子节点，如下图：
F
A
B
当 node 移动到F的时候，find(node.left, A) && find(node.left, B) 为 false,
node不变仍为F；find(node.right, A) 和 find(node.left, B) 均为 true。则此时
node 移动到A，find(node.right, A) 为false，find(node.right, B) 为true，则结
果仍为 false，node 不变仍为A。于是返回A，应是正确答案。
实际上我自己测试了这种父子节点的情况，结果是正确的……
【在 z***y 的大作中提到】
: A、B是父子节点，他们是肯定在同一侧的。
| m******3
发帖数: 6 | | c*******7
发帖数: 438 | 5 你这个的performance是不是有点差？为什么不用dfs？ | w******n
发帖数: 61 | 6 超时了？感觉这个方法不是o（n）啊。dfs记下路径比较是o（n）。
【在 w*********2 的大作中提到】
: 我考虑过这种情况了。
: 假设A是F的右子节点，B是A的右子节点，如下图：
: F
:
: A
:
: B
: 当 node 移动到F的时候，find(node.left, A) && find(node.left, B) 为 false,
: node不变仍为F；find(node.right, A) 和 find(node.left, B) 均为 true。则此时
: node 移动到A，find(node.right, A) 为false，find(node.right, B) 为true，则结
|
|
