[LeetCode] 156. Binary Tree Upside Down

Posted on | In

Problem

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: [1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5

Output: return the root of the binary tree [4,5,2,#,#,3,1]

   4
  / \
 5   2
    / \
   3   1

Clarification:

Confused what [4,5,2,#,#,3,1] means? Read more below on how binary tree is serialized on OJ.

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

1
2
3
4
5
6
7
   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as [1,2,3,#,#,4,#,#,5].

Explanation

  1. After we do a unside down opertion, original tree’s left child becomes the root node, right child becomes the left child, and the root node becomes the right child. In other words, it’s clock-wise rotate.

  2. We can use recursion to solve this method. The base case is if the root node or the right child doesn’t exist, then we just return root. We can recursively pass the left child to the main function and we return res. Now, the left child tree finish upside down. That means the original root node’s left child (root.left) node is in the bottom right side of the finished upside tree. We think of it as the root node, then original root node’s right child becomes its left child root.left.left = root.right, and original node become its right child root.left.right = root.

  3. Next, we remove original root node’s left and right child connection. root.left = null and root.right = null. At the end, return res.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if (root == null || root.left == null) {
            return root;
        }
        TreeNode l = root.left, r = root.right;
        TreeNode res = upsideDownBinaryTree(l);
        root.left.left = r;
        root.left.right = root;

        root.left = null;
        root.right = null;
        return res;
    }
}