Given the root of a binary tree, invert the tree, and return its root. Inversion means every node's left and right children are swapped — recursively throughout the entire tree.
root = [4,2,7,1,3,6,9][4,7,2,9,6,3,1]root = [2,1,3][2,3,1]root = [1][1]root == null → return nulltmp=root.left; root.left=root.right; root.right=tmpinvertTree(root.left)invertTree(root.right)rootWe swap a node's children before recursing into them. This is safe because the swap is an O(1) pointer exchange — no recursion needed first. After swapping, we recurse into what is now root.left (which was previously root.right) and vice versa. Every node is visited exactly once → O(n) time, O(h) stack space where h is the tree height.
You might try to rebuild a new tree level by level in reverse order. But the mirror image is just one swap per node, so no new tree is needed.
At every node, swap its left and right child. Then invert the left subtree and the right subtree in the same way. A null node needs no work, so it is the base case. The order of the swap and the recursive calls does not matter, as long as every node is swapped exactly once.
Swap the children, then recurse into both sides. A breadth first search with the same swap works too.
Run the animation above on your own input, or watch the 1:50 video explanation of Invert Binary Tree with a dry run and Java code.