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}, 1 / \ 2 3 / \4 5
return the root of the binary tree [4,5,2,#,#,3,1].
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 child10 TreeNode* right = node -> right; // old right child11 node -> left = sibling; // new left child is old right sibling12 node -> right = parent; // new right child is old parent13 return upsideDown(left, node, right); // node is left's parent and right is left's sibling14 }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 child10 run -> left = sibling; // new left child is old right sibling11 run -> right = parent; // new right child is old parent12 parent = run;13 run = left;14 sibling = right;15 }16 return parent;17 }18 };