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

解析

这道题没有太大实际意义。题意理解也比较费尽。要求根据题意会写代码，that‘s it

思路

recursively upside down binary tree. So right child is become root left child’s left child; root becomes root left child’s right child; and return current root.

After recursively call, we return the old root node, where is the new root? you can find it by getting its left most left child or simplify get it from recursively call when root.left== null.

图解

代码

// O(N)time, O(N)space stack
class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        if(root == null || root.left ==null) return root;
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        root.left.left = root.right;
        root.left.right = root;
        root.left = null;
        root.right = null;
        return newRoot;
    }
}