TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write flip_tree(root) -> TreeNode: turn the tree into its mirror image, as if you held it up to a mirror standing beside it. Every node's left and right children trade places, all the way down. Return the root of the flipped tree (changing the given nodes in place is fine). An empty tree (None) stays empty.
# 5 5
# / \ / \
# 3 8 -> 8 3
# / \ \ / / \
# 1 4 9 9 4 1
flip_tree(root) # the tree on the right
flip_tree(None) # None
- Up to 5,000 nodes; values are arbitrary integers and may repeat.
- Aim for O(n) time.
Show hint
Flipping a whole tree is the same job as flipping its two subtrees and then swapping them at the root.