A 16 ms C++ solution


  • 0

    These type of problems are quite difficult for me. Finally I figured out a recursive solution.

    TreeNode *helper(vector<int>& in, vector<int>& post, int le, int ri, int& it)//'&it' is key point, make sure it is a static variable
    
    {
    	if (le > ri)
    		return 0;
    	TreeNode *root = new TreeNode(post[it]);
    	int i;
    	for (i = ri; i >= 0; --i)
    	{
    		if (in[i] == post[it])
    			break;
    	}
    	--it; //move 'it' to next element in postorder array when new TreeNode() is created.
    	root->right = helper(in, post, i + 1, ri, it);
    	root->left = helper(in, post, le, i - 1, it);
    	return root;
    }
    TreeNode* buildTree(vector<int>& in, vector<int>& post) 
    {
    	if (!post.size())
    		return 0;
    	int ri = post.size() - 1;
    	int le = 0;
    	int it = ri;
    	return helper(in, post, le, ri, it);
    }

Log in to reply
 

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