LeetCode 889. 已知前序&后序 求二叉树（不唯一）

示例：

输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        unordered_map<int,int> m;
        for(int i = 0; i < pre.size(); ++i)
        	m[pre[i]] = i;
        return bt(pre,0,pre.size()-1,post,0,post.size()-1,m);
    }

    TreeNode* bt(vector<int>& pre,int preS, int preE,vector<int>& post, int postS, int postE, unordered_map<int,int> &m)
    {
    	if(preS > preE)
    		return NULL;
    	if(preS == preE)
        {
    	    return new TreeNode(pre[preS]);
        }
    	TreeNode *root = new TreeNode(pre[preS]);
    	int leftlen = m[post[postE-1]]-preS-1;
    	int rightlen = preE-m[post[postE-1]]+1;
    	root->left = bt(pre,preS+1,preS+leftlen,post,postS,postS+leftlen-1,m);
    	root->right = bt(pre,m[post[postE-1]],preE,post,postE-rightlen,postE-1,m);
    	return root;
    }
};