The Leetcode June'20 challenge has begun with a tree inversion problem. The problem is pretty simple, invert a tree or in other words create a mirror image of the tree.
The implementation of the tree is given and is nothing different from the usual, containing left and right child for each node. To understand the problem a basic knowledge of binary tree is required. However, if you are well-versed with this data structure, the solution is quite easy to figure out.
Here's a link to the problem, try it on your own before you go through the solution below. (https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/539/week-1-june-1st-june-7th/3347/)
Approach:
Travelling downward from the root of the tree, swap left and right child and call this same function recursively for each node of the tree. Pretty simple, eh?
C++ code:
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
TreeNode *i= root;
TreeNode *temp=NULL;
while(i!=NULL)
{
temp=i->left;
i->left=i->right;
i->right=temp;
TreeNode *l=invertTree(i->left);
TreeNode *r=invertTree(i->right);
if(i==root)
break;
}
return root;
}
};
Top comments (2)
Thanks for the problem and solution. Here is my solution,
Note: It changes the tree in-place.
gotta say your solution is prettier( and efficient), thanks for sharing!