Problem description:

Given the root of a binary tree, turn the tree upside down and return the new root.

You can turn a binary tree upside down with the following steps:

  1. The original left child becomes the new root.
  2. The original root becomes the new right child.
  3. The original right child becomes the new left child.

https://assets.leetcode.com/uploads/2020/08/29/main.jpg

The mentioned steps are done level by level, it is guaranteed that every node in the given tree has either 0 or 2 children.

Example 1:

https://assets.leetcode.com/uploads/2020/08/29/updown.jpg

1
2
Input: root = [1,2,3,4,5]
Output: [4,5,2,null,null,3,1]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

Constraints:

  • The number of nodes in the tree will be in the range [0, 10].
  • 1 <= Node.val <= 10
  • Every right node in the tree has a sibling (a left node that shares the same parent).

Solution:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/216fc4c7-bf7d-46f8-a7fc-1b5b2599fcd4/Untitled.png

As the recursive solution, we will keep recurse on the left child and once we are are done, we found the newRoot, which is 4 for this case. At this point, we will need to set the new children for node 2, basically the new left node is 3, and right node is 1. Here is the recursive solution:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        if not root or not root.left:
            return root
        
        newRoot = self.upsideDownBinaryTree(root.left)
        root.left.left = root.right
        root.left.right = root
        root.left = None
        root.right = None
        return newRoot

For the iterative solution, it follows the same thought, the only thing we need to pay attention to is to save the node information that will be overwritten.

https://assets.leetcode.com/users/images/cc5350ec-0158-4582-9163-fcbe37dd5cd6_1601421096.4278862.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
        # iterative
        cur = root
        pre = next = tmp = None
        
        while cur:
            next = cur.left
            cur.left = tmp
            tmp = cur.right
            cur.right = pre
            
            pre = cur
            cur = next
        return pre

time complexity: $O()$
space complexity: $O()$
reference:
https://leetcode.com/problems/binary-tree-upside-down/discuss/49406/Java-recursive-(O(logn)-space)-and-iterative-solutions-(O(1)-space)-with-explanation-and-figure

related problem: