A straightforward way -- O(n) time


  • 3
    //we pass the indices of post/inorder vector, 
    //which represents the begin and end of the sub tree
    TreeNode* helper2( vector<int>& postorder, int poL, int poR,
    				  vector<int>& inorder, int inL, int inR, map<int, int>& map)
    {
    	if( poL > poR || inL > inR )
    		return NULL;
    	//everytime we insert the post order of sub tree's last element as root
    	TreeNode* root = new TreeNode( postorder[poR] );
    	int index = map[root->val];
    	//( index - inL ) means the length of the left subtree,
    	//we calculate the indices of the begin and end of the subtree in post/in order
    	root->left = helper2( postorder, poL, poL + ( index - inL ) - 1, inorder, inL, index-1, map );
    	root->right = helper2( postorder, poL+ ( index - inL ), poR-1, inorder, index+1, inR, map );
    	return root;
    
    }
    
    class Solution {
    public:
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        
        if( postorder.size() == 0 || inorder.size() == 0 )
    		return NULL;
    	map<int, int> map;
    	//faster to get the indices and length of subtree
    	for( int i = 0; i < inorder.size(); i++ )
    		map[inorder[i]] = i;
    	return helper2(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1, map);
            
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.