226. Invert Binary Tree - June day 1
Inspiration of this problem comes from Max Howel's interview experience with Google described in this tweet.
Lets jump to the problem
The idea is to invert every subtree, let's start with a simple example.
As you can see in the below example, just swap children nodes and we will have the resulting tree.
It gets a little trickier with bigger trees, however the principle is basic.
- Start with root node
- Swap its children
- Perform the same process on all nodes
Let's this in an example:
Now let's swap its children:
- Swap subtrees 3 and 7
- Swap subtrees of node 7: 6 and 9
- Swap subtrees of node 3: 2 and 4
Resulting tree will look like this:
This can be solved using either depth first search or breadth first search, we will solve it with BFS to avoid recursion overhead:
- Create queue
- Add root to the queue
- While queue is not empty
- Remove first node from the queue
- If node is not null (not a lead node)
- Swap its left and right nodes
- Add left and right to queue
class Solution {
public TreeNode invertTree(TreeNode root) {
var queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()) {
var node = queue.removeFirst();
if(node != null) {
var temp = node.left;
node.left = node.right;
node.right = temp;
queue.add(node.left);
queue.add(node.right);
}
}
return root;
}
}