You are given root, the root of a binary tree (or nothing, for an empty tree).
Turn the tree into its mirror image: at every node, the left and right subtrees trade places. Return the root of the mirrored tree.
Trees are written in level order, row by row from the top, with null where a node is missing:
[4, 2, 7, 1, 3] is 4 at the root, 2 and 7 below it, then 1 and 3 under 2.
Example 1
- Input
- root = [4, 2, 7, 1, 3, 6, 9]
- Output
- [4, 7, 2, 9, 6, 3, 1]
Example 2
- Input
- root = [5, 3]
- Output
- [5, null, 3]
Constraints
- The tree holds 0 to 100 nodes.
- Every value is between −100 and 100.
Show the pattern
Trees
A tree's mirror is its root with the mirrors of its two subtrees swapped. The answer for a node comes straight from the answers for its children: recursion.
See trees in a visualiserShow the approach
Recurse: an empty tree is its own mirror. Otherwise mirror the left subtree and the right subtree, then attach the mirrored left as the new right child and the mirrored right as the new left child. Each node is visited once.
Time: O(n) · Space: O(h) for the recursion, h the tree's height