[LeetCode] 156. Binary Tree Upside Down

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.

For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

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

   4
  / \
 5   2
    / \
   3   1  

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Thought process:

After the flip, root and root.right will become siblings, and the left most child will become the new root. The idea is to traverse the tree to the left. As we traverse, we make root.left the new root, root.right the left child of new root, and root itself the right child of new root.

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 25

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode upsideDownBinaryTree(TreeNode root) { if (root == null || root.left == null) { return root; } TreeNode left = upsideDownBinaryTree(root.left); root.left.left = root.right; root.left.right = root; root.left = null; root.right = null; return left; } }

Time complexity:
Say n = number of nodes, the time complexity is O(n).