Easy to understand: Iterative Solution: O(n): C++


#1
TreeNode* Solution::buildTree(vector<int> &A, vector<int> &B) {
    unordered_map<int, int> mapping;
    
    int index = 0;
    for (const auto &ele: B) {
        mapping[ele] = index++;
    }
    
    stack<pair<TreeNode *, int> > stck;
    TreeNode *root = new TreeNode(A[0]);
    stck.push(make_pair(root, mapping[A[0]]));
    
    for (int i = 1; i < A.size(); i++) {
        TreeNode *node = new TreeNode(A[i]);

        if (stck.top().second > mapping[A[i]]) {
            stck.top().first->left = node;
        } else {
            TreeNode *lastNode = nullptr;
            
            while (!stck.empty() and stck.top().second < mapping[A[i]]) {
                lastNode = stck.top().first;
                stck.pop();
            }
            
            lastNode->right = node;
        }
        
        stck.push(make_pair(node, mapping[A[i]]));
    }
    
    return root;
}