Invert Binary Tree
EasyThe problem
Turn a binary tree into its mirror image, so that every node's left and right children trade places. Return the root of the flipped tree.
- Example 1Input: root = [4, 2, 7, 1, 3, 6, 9]Output: [4, 7, 2, 9, 6, 3, 1]
Every node swaps its two children, all the way down.
- Example 2Input: root = [2, 1, 3]Output: [2, 3, 1]
Limits
- 0 ≤ number of nodes ≤ 100
- An empty tree stays empty (return nil)
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
If both subtrees are already inverted, what is the only thing left to do at this node?
The idea
Recursively invert left and right, then swap them.
Target: O(n) time, O(h) space
Go function shape
func invertTree(root *TreeNode) *TreeNodeReference solution
Tested with go test. Try it yourself first, then compare.
// InvertTree: mirror the tree.
func InvertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = InvertTree(root.Right), InvertTree(root.Left)
return root
}