t**n
发帖数: 272 | 1 Given a binary tree, how would you write program for getting mirror image of
tree in O(n) time? Is it possible ? Assume you have no constraints on space.
我只能想到递归:
Mirror(Node* p){
Mirror(p->left);
Mirror(p->right);
ExchangeLeftRight(p);
}
这个复杂度应该怎么算? |
l*******t
发帖数: 642 | 2 Think how many times each node will be touched ... |
b******v
发帖数: 1493 | 3 T(n)=2*T(n/2)+1
根据master theorem, 复杂度是O(n)
of
space.
【在 t**n 的大作中提到】
: Given a binary tree, how would you write program for getting mirror image of
: tree in O(n) time? Is it possible ? Assume you have no constraints on space.
: 我只能想到递归:
: Mirror(Node* p){
: Mirror(p->left);
: Mirror(p->right);
: ExchangeLeftRight(p);
: }
: 这个复杂度应该怎么算?
|
c******f
发帖数: 2144 | |
c******f
发帖数: 2144 | 5 这个应该等价二叉树的遍历
那么T(n)=2T(n/2)+O(1)
适用master theory的其中一种情况
当有ε > 0， 使得f(n)=O(n^(logb(a)-ε))则T(n)=Theta(n^logb(a))
这里a=2,b=2,logb(a)=1, f(n)=O(1), 所以存在epsilon=1
那么 T（n）=Theta(n) |
z*******y
发帖数: 578 | 6 Check the code below:
void mirror(struct node* node) {
if (node==NULL) {
return;
}
else {
struct node* temp;
// do the subtrees
mirror(node->left);
mirror(node->right);
// swap the pointers in this node
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
|
f**r
发帖数: 865 | 7 That's an O(N) algorithm (each node is only touched once). Be careful about
the boundary conditions though (i.e. check for NULL for p->left & p->right).
of
space.
【在 t**n 的大作中提到】
: Given a binary tree, how would you write program for getting mirror image of
: tree in O(n) time? Is it possible ? Assume you have no constraints on space.
: 我只能想到递归:
: Mirror(Node* p){
: Mirror(p->left);
: Mirror(p->right);
: ExchangeLeftRight(p);
: }
: 这个复杂度应该怎么算?
|
