LeetCode Q156: 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  

Solution:
The most bottom left node will serve as a root in new tree. Using post-traversal. Remember that the right not will not have any children, so the recursion only apply to left node.

	/**
	* 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:
	void helper(TreeNode* l, TreeNode* r, TreeNode*& newroot){
	if(l->left==NULL&&l->right==NULL){
	newroot=l;
	l->left=r;
	return;
	}
	helper(l->left, l->right, newroot);
	l->left->right=l;
	l->left=r;
	}
	TreeNode* upsideDownBinaryTree(TreeNode* root) {
	TreeNode* newroot=NULL;
	if(root==NULL)
	return newroot;
	if(root->left==NULL&&root->right==NULL){
	newroot=root;
	return newroot;
	}
	helper(root->left, root->right, newroot);
	root->left->right=root;
	root->left=NULL;
	root->right=NULL;
	return newroot;
	}
	};

view raw Q156BinaryTreeUpsideDown.cpp hosted with ❤ by GitHub

Round 2 solution:

	/**
	* 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* helper(TreeNode* root){
	if(root->left==NULL&&root->right==NULL)
	return root;
	TreeNode* l = helper(root->left);
	l->left = root->right;
	l->right = root;
	root->left=NULL;
	root->right=NULL;
	return root;
	}
	TreeNode* upsideDownBinaryTree(TreeNode* root) {
	if(root==NULL)
	return root;
	TreeNode* newRoot=root;
	while(newRoot->left!=NULL)
	newRoot=newRoot->left;
	helper(root);
	return newRoot;
	}
	};

view raw Q156Rnd2.cpp hosted with ❤ by GitHub