Mirroring a binary tree, a common question nowadays to understand whether the candidate knows about tree traversal.
![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjaI515oaUX-Qdr8f3FrDa8kYcADuS5zgRMK7FFJmcAUDf3OQ7dFiAtnZldLHOJ-CrFh-MM-Ojjk6QBeRSFdXuhbrkoiIr9bkYoJ142TeW0weaGBvxXs4raIpqwEHhmnrmhuIQT45olyK8/s1600/12_Figure1.PNG)
https://www.geeksforgeeks.org/write-an-efficient-c-function-to-convert-a-tree-into-its-mirror-tree/
http://analgorithmaday.blogspot.com/2013/05/mirror-binary-tree.html
Correct code for creating mirrored tree, in-place
https://github.com/yadongwen/Company1-InterviewQuestions-Answers-Java/blob/master/mirror%20of%20binary%20tree.java
The order(swap or put to queue) doesn't matter.
public static void mirrorIterative(TreeNode t) {
if(t == null) return;
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
q.add(t);
while(!q.isEmpty()) {
TreeNode tr = q.poll();
if(tr.left != null) q.add(tr.left);
if(tr.right != null) q.add(tr.right);
TreeNode temp = tr.left;
tr.left = tr.right;
tr.right = temp;
}
}
http://algorithmproblems.blogspot.com/2012/12/are-two-binary-trees-mirror-image-of.html
Are two Binary Trees mirror image of each other?
Read full article from An Algorithm a Day: Mirror a binary tree
Correct code for creating mirrored tree, in-place
- do a post order traversal to read the full tree into the recursion stack
- do the primitive swap operationhttps://www.geeksforgeeks.org/write-an-efficient-c-function-to-convert-a-tree-into-its-mirror-tree/
(1) Call Mirror for left-subtree i.e., Mirror(left-subtree) (2) Call Mirror for right-subtree i.e., Mirror(right-subtree) (3) Swap left and right subtrees. temp = left-subtree left-subtree = right-subtree right-subtree = temp
Tree* mirror(Tree* node)
{
if(node == NULL)
return NULL;
mirror(node->left);
mirror(node->right);
Tree *tmp = node->left;
node->left = node->right;
node->right = tmp;
return node;
}Corrected code for reproduction of mirrored tree, as a copy
Tree* mirror(Tree* node)
{
if(node == NULL)
return NULL;
Tree *newNode = createNode(node->data);
newNode->left = mirror(node->right);
newNode->right = mirror(node->left);
return newNode;
}
struct node |
02 | { |
03 | int value; |
04 | struct node* left; |
05 | struct node* right; |
06 | }; |
07 |
08 |
09 | struct node *mirrorTree( struct node *root) |
10 | { |
11 | struct node *temp; |
12 | |
13 | if (root==NULL) |
14 | return (NULL); |
15 | |
16 | temp = ( struct node *) malloc ( sizeof ( struct node)); |
17 | temp->value = root->value; |
18 |
19 | temp->left = mirrorTree(root->right); |
20 | temp->right = mirrorTree(root->left); |
21 |
22 | return (temp); |
23 | } |
- do a post order traversal to read the full tree into the recursion stack
Tree* mirror(Tree* node)
{
if(node == NULL)
return NULL;
mirror(node->left);
mirror(node->right);
Tree *tmp = node->left;
node->left = node->right;
node->right = tmp;
return node;
}
Iteratively mirror a tree
http://haixiaoyang.wordpress.com/2012/07/14/iteratively-mirror-a-tree/
void
IterativeMirror(NODE* pRoot)
{
if
(NULL == pRoot)
return
;
stack<NODE*> stk;
stk.push(pRoot);
while
(!stk.empty())
{
NODE* pTop = stk.top();
stk.pop();
swap(pTop->pLft, pTop->pRgt);
if
(pTop->pLft != NULL)
stk.push(pTop->pLft);
if
(pTop->pRgt != NULL)
stk.push(pTop->pRgt);
}
}
The order(swap or put to queue) doesn't matter.
public static void mirrorIterative(TreeNode t) {
if(t == null) return;
LinkedList<TreeNode> q = new LinkedList<TreeNode>();
q.add(t);
while(!q.isEmpty()) {
TreeNode tr = q.poll();
if(tr.left != null) q.add(tr.left);
if(tr.right != null) q.add(tr.right);
TreeNode temp = tr.left;
tr.left = tr.right;
tr.right = temp;
}
}
void tree_mirror( struct node* node) |
02 | { |
03 | struct node *temp; |
04 |
05 | if (node==NULL) |
06 | { |
07 | return ; |
08 | } |
09 | else |
10 | { |
11 | tree_mirror(node->left); |
12 | tree_mirror(node->right); |
13 |
14 | // Swap the pointers in this node |
15 | temp = node->left; |
16 | node->left = node->right; |
17 | node->right = temp; |
18 | } |
19 | } |
Are two Binary Trees mirror image of each other?
boolean areMirrorTrees(BinaryTree a, BinaryTree b) { if (a == null && b == null) { return true; } if (a == null || b == null) { return false; } return a.data == b.data && areMirrorTrees(a.left, b.right) && areMirrorTrees(a.right, b.left); }http://www.acmerblog.com/offer11-2964.html
10 | typedef struct Node { |
11 | struct Node * l; |
12 | struct Node * r; |
13 | int data; |
14 | }* pNode, Node; |
15 | char temp[2]; |
16 | Node tree[1001]; |
17 | //先右后左输出二叉树 |
18 | void print(pNode root) { |
19 | if (root == 0) |
20 | return ; |
21 | printf ( " %d" , root->data); |
22 | print(root->r); |
23 | print(root->l); |
24 | } |
25 | int main() { |
26 | while (~ scanf ( "%d" , &n)) { |
27 | for ( i = 1; i <= n; i++) { |
28 | scanf ( "%d" , &tree[i].data); |
29 | tree[i].l = tree[i].r = 0; |
30 | } |
31 | for ( i = 1; i <= n; i++) { |
32 | scanf ( "%s %d" , temp, &a); |
33 | if (temp[0] == 'd' ) { |
34 | tree[i].l = &tree[a]; |
35 | scanf ( "%d" , &a); |
36 | tree[i].r = &tree[a]; |
37 | } else if (temp[0] == 'l' ) |
38 | tree[i].l = &tree[a]; |
39 | else if (temp[0] == 'r' ) |
40 | tree[i].r = &tree[a]; |
41 | } |
42 | if (n) { |
43 | printf ( "%d" , tree[1].data); //由于空格判断,根节点单独输出 |
44 | print(tree[1].r); |
45 | print(tree[1].l); |
46 | puts ( "" ); |
47 | } else |
48 | puts ( "NULL" ); |
49 | } |
50 | return 0; |
51 | } |