105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

class Solution {
public:
    int preindex;
    unordered_map<int,int> map;
    TreeNode* traversal(int left,int right,vector<int>& inorder,vector<int>& preorder)
    {
        //无元素是返回
        if(left>right)return NULL;
        int rootValue = preorder[preindex];
        TreeNode* root = new TreeNode(rootValue);
        int midIndex = map[rootValue];
        preindex++;
        root->left = traversal(left,midIndex-1,inorder,preorder);
        root->right = traversal(midIndex+1,right,inorder,preorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        preindex = 0;
        //哈希表记录元素的索引
        for(int i=0;i<inorder.size();i++)
            map[inorder[i]] = i;
        return traversal(0,inorder.size()-1,inorder,preorder);
    }
};