Given the root of a binary tree, mirror it: swap the left and right child of every node. Return the root of the mirrored tree.
Example 1
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2
Input: root = [2,1,3]
Output: [2,3,1]
Constraints
- The number of nodes is in the range 0 to 100
- -100 <= Node.val <= 100
Hints
Frequently asked at: Google, Amazon, Adobe
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
There is no slow version worth writing here: every node must be touched, so O(n) is the floor. The insight is that mirroring a tree is the same as swapping the two children of the root and then mirroring each of those subtrees. Recursion expresses that in a few lines. An iterative BFS that swaps the children of every node it pops gives the same result.
Algorithm
- If
rootis null, return null. - Swap
root.leftandroot.right. - Recursively invert
root.leftandroot.right. - Return
root.
Time:
O(n)Space: O(h) recursion depthInterview tip: Be careful when writing
root.left = invert(root.right); root.right = invert(root.left): the second line reads the already overwritten left child. Save one side in a temporary variable first.class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None # Tuple assignment evaluates the right side first, so nothing is lost root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return rootCtrl + Enter runs the examples