c*******r
发帖数: 309 | 1 public class LowestCommonAncestor {
public boolean cover(Node root, Node node) {
if (root == null)
return false;
if (root == node)
return true;
return cover(root.left, node) || cover(root.right, node);
}
public Node Ancestor(Node root, Node node1, Node node2) {
if (root == null)
return root;
if (cover(root.left, node1) && cover(root.left, node2))
return Ancestor(root.left, node1, node2);
if (cover(root.right, node1) && cover(root.right, node2))
return Ancestor(root.left, node1, node2);
return root;
}
}
这个复杂度cover()是LogN,再recursion一下时间复杂度是多少啊？ | U***5
发帖数: 2796 | 2 Worst case O(N^2)
LCA(3, 6)
1
\
2
\
3
\
6
【在 c*******r 的大作中提到】
: public class LowestCommonAncestor {
: public boolean cover(Node root, Node node) {
: if (root == null)
: return false;
: if (root == node)
: return true;
: return cover(root.left, node) || cover(root.right, node);
: }
: public Node Ancestor(Node root, Node node1, Node node2) {
: if (root == null)
| c********t
发帖数: 5706 | 3 nlogn, 因为对每个node都要调用cover
再想想，这题有O(n)解法
【在 c*******r 的大作中提到】
: public class LowestCommonAncestor {
: public boolean cover(Node root, Node node) {
: if (root == null)
: return false;
: if (root == node)
: return true;
: return cover(root.left, node) || cover(root.right, node);
: }
: public Node Ancestor(Node root, Node node1, Node node2) {
: if (root == null)
| U***5
发帖数: 2796 | 4 Ancestor第二个recursion好像有个typo?
【在 c*******r 的大作中提到】
: public class LowestCommonAncestor {
: public boolean cover(Node root, Node node) {
: if (root == null)
: return false;
: if (root == node)
: return true;
: return cover(root.left, node) || cover(root.right, node);
: }
: public Node Ancestor(Node root, Node node1, Node node2) {
: if (root == null)
| t***e
发帖数: 27 | 5 There is a O(n) time worst case algorithm in https://code.google.com/p/
elements-of-programming-interviews/source/browse/trunk/Lowest_common_
ancestor_no_parent_template.cpp
It is the solution from Elements of Programming Interviews: 300 Questions
and Solutions http://www.amazon.com/dp/1479274836/. | c*******r
发帖数: 309 | 6 这个average复杂度难道不是O(logN*logN)？ cover()复杂度logN, recursion logN次
（层数). worse case是O(N2)
【在 c********t 的大作中提到】
: nlogn, 因为对每个node都要调用cover
: 再想想，这题有O(n)解法
| c********t
发帖数: 5706 | 7 我说错了，应该是O(N), CC150上有原题解释。对一个balanced tree，基本上是4N
cover本身也是一个O(n)的
但有优化解法，不重复计算 。
【在 c*******r 的大作中提到】
: 这个average复杂度难道不是O(logN*logN)？ cover()复杂度logN, recursion logN次
: （层数). worse case是O(N2)
|
|
