Problem
Change a tree so that the roles of the left and right pointers are swapped at every node.
Example
So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.
Recursive solution
Iterative solution
Here is the solution:
This is similar to level order traversal.Thanks.
Change a tree so that the roles of the left and right pointers are swapped at every node.
Example
So the tree...
4
/ \
2 5
/ \
1 3
is changed to...
4
/ \
5 2
/ \
3 1
The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.
Recursive solution
/* Change a tree so that the roles of the left and right pointers are swapped at every node. So the tree... 4 / \ 2 5 / \ 1 3 is changed to... 4 / \ 5 2 / \ 3 1 */ 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; } }
Iterative solution
Here is the solution:
void MirrorIterative(Node * tree) { if (!tree) return; Stack s; s.push(tree); while(!s.empty()) { Node * current = s.pop(); // Swap the children // Node * temp = current->right; current->right = current->left; current->left = temp; // Push the children on the stack // if (current->right) s.push(current->right); if (current->left) s.push(current->left); } }
This is similar to level order traversal.Thanks.
0 comments:
Post a Comment