[LeetCode] Binary Tree Upside Down

Problem Description:

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},

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

This problem seems to be tricky at first glance. Well, let's analyze the above example carefully. We can immediately see that there is a reversed correspondence between the two trees, which are the 1 -> 2 -> 4 in the tree above and the 4 -> 2 -> 1 in the tree below. Moreover, for each node along the left path 1 -> 2 -> 4 in the original tree, its new left child is its original right sibling and its new right child is its original parent.

Now we can write down the following recursive code.

 1 class Solution {
 2 public:
 3     TreeNode* upsideDownBinaryTree(TreeNode* root) {
 4         return upsideDown(root, NULL, NULL);    // start from root
 5     }
 6 private:
 7     TreeNode* upsideDown(TreeNode* node, TreeNode* parent, TreeNode* sibling) {
 8         if (!node) return parent;
 9         TreeNode* left = node -> left;          // old left child
10         TreeNode* right = node -> right;        // old right child
11         node -> left = sibling;                 // new left child is old right sibling
12         node -> right = parent;                 // new right child is old parent
13         return upsideDown(left, node, right);   // node is left's parent and right is left's sibling
14     }
15 };

The above recursive code can be turned into the following iterative code easily.

 1 class Solution {
 2 public:
 3     TreeNode* upsideDownBinaryTree(TreeNode* root) {
 4         TreeNode* run = root;
 5         TreeNode* parent = NULL;
 6         TreeNode* sibling = NULL;
 7         while (run) {
 8             TreeNode* left = run -> left;   // old left child
 9             TreeNode* right = run -> right; // old right child
10             run -> left = sibling;          // new left child is old right sibling
11             run -> right = parent;          // new right child is old parent
12             parent = run;
13             run = left;
14             sibling = right;
15         }
16         return parent;
17     }
18 };