156. Binary 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

Thoughts:

1. Recursively:

   1. Traverse all the way to the left until the left child of the curNode's left child is null.

   2. Perform rotation: cur->left->left = cur -> right; cur->left->right = cur; cur - > left = NULL; cur->right = NULL;

   3. return the newRoot; (originally, cur->left).

2. Iteratively: until current Node is NULL:

   1. save left child as next node to explore, set leftChild to be the current sibling node,

   2. set sibling node to be current right child's node (for the next iteration)

   3. set right child to be the predecessor node

Code 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        if(!root || !root -> left) return root;

        TreeNode * newRoot = upsideDownBinaryTree(root -> left);
        root -> left -> left = root -> right;
        root -> left -> right = root;
        root -> left = NULL;
        root -> right = NULL;
        return newRoot;
    }
};

Code 2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* upsideDownBinaryTree(TreeNode* root) {
        TreeNode* cur = root, * pre = NULL, * next= NULL, * sib = NULL;

        while(cur){
            next = (cur->left);
            cur-> left = sib;
            sib = cur -> right;
            cur -> right = pre;

            pre = cur;
            cur = next;
        }

        return pre;
    }
};

Special Thanks to yfcheng's solution and explanation