Invert binary tree.
EasyUnlock detailed company stats for this questionUpgrade
Given the root of a binary tree, invert it by swapping the left and right children of every node, and return its root.
Trees in the examples and tests are written in level order, with null for a missing child.
Example 1
Input: root = [4, 2, 7, 1, 3, 6, 9] Output: [4, 7, 2, 9, 6, 3, 1] 4 4 / \ / \ 2 7 -> 7 2 / \ / \ / \ / \ 1 3 6 9 9 6 3 1
Example 2
Input: root = [2, 1, 3] Output: [2, 3, 1]
Constraints
- The tree has between
0and100nodes. -100 <= Node.val <= 100
Approach
An inverted tree is the original root with its two subtrees swapped, and each of those subtrees inverted too. So invert the left and right subtrees recursively, attach them to the opposite sides, and return the root. An empty tree inverts to itself, which is the base case.
Steps
- If
rootis empty, return it. - Invert the left subtree and the right subtree.
- Attach the inverted right subtree on the left and the inverted left subtree on the right.
- Return
root.
Complexity
- Time:
O(n). Each node is visited once. - Space:
O(h)for the recursion stack, wherehis the height of the tree.
Common mistakes
- Overwriting
root.leftbefore saving it. Keep the old left subtree in a temporary variable, or use tuple assignment in Python. - Swapping only the root's children. Every node's children need to be swapped, so recurse into both subtrees.
Interview experiences
1 sharedRelated questions
Re-root a binary tree.Vertical Traversal of a Binary TreeFind Leaves of Binary TreeRelated courses

Course

Course

