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