c*******r
发帖数: 309 | 1 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;
}
这个算法的复杂度到底是多少啊？ 我感觉是O(logN*logN)， 因为cover复杂度是logN,
然后ancestor方法也是LogN | j*****y
发帖数: 1071 | 2 cover 是 n, ancestor 也是 n 吧 ?
【在 c*******r 的大作中提到】
: 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;
| c*******r
发帖数: 309 | | d*********g
发帖数: 154 | 4
ancestor是logn 吧？每次都往下走一层
【在 j*****y 的大作中提到】
: cover 是 n, ancestor 也是 n 吧 ?
| w****g
发帖数: 727 | | c*****a
发帖数: 808 | 6 感觉是n^2吧，假设tree只有left child...一直往左找
而且好像有bug. return Ancestor(root.left, node1, node2);用了2次..... |
|
