105.从前序与中序遍历序列构造二叉树 (Medium)*

class Solution {
public:
    TreeNode *build(vector<int>& preorder, int rootPos, vector<int>& inorder, int start, int end, 
        unordered_map<int, int>& posMap) {
        if(start > end) {
            return nullptr;
        }
        TreeNode *root = new TreeNode(preorder[rootPos]);
        int pos = posMap[preorder[rootPos]];
        root->left = build(preorder, rootPos + 1, inorder, start, pos - 1, posMap);
        root->right = build(preorder, rootPos + pos - start + 1, inorder, pos + 1, end, posMap);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) {
            return nullptr;
        }
        unordered_map<int, int> posMap;
        for(int i = 0; i < inorder.size(); i++) {
            posMap[inorder[i]] = i;
        }
        return build(preorder, 0, inorder, 0, inorder.size() - 1, posMap);
    }
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0) {
            return nullptr;
        }
        stack<TreeNode*> helpStack;
        TreeNode *root = new TreeNode(preorder[0]);
        helpStack.push(root);
        // i 为前序序号，j 为中序序号
        for(int i = 1, j = 0; i < preorder.size(); i++) {
            TreeNode *back = nullptr, *cur = new TreeNode(preorder[i]);
            while(!helpStack.empty() && helpStack.top()->val == inorder[j]) {
                back = helpStack.top();
                helpStack.pop();
                j++;
            }
            if(back == nullptr) {
                helpStack.top()->left = cur;
            }else {
                back->right = cur;
            }
            helpStack.push(cur);
        }
        return root;
    }
};