889. Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

• 1 <= pre.length == post.length <= 30

• pre[] and post[] are both permutations of 1, 2, ..., pre.length.

• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

TreeNode* helper(vector<int>& pre, int preL, int preR, vector<int>& post, int postL, int postR, unordered_map<int, int>& m) {
    if (preL > preR || postL > postR) return nullptr;
    TreeNode* node = new TreeNode(pre[preL]);
    if (preL == preR) return node;
    // the corresponding index in post-order traversal
    int idx = m[pre[preL + 1]];
    node->left = helper(pre, preL + 1, preL + 1 + (idx - postL), post, postL, idx, m);
    node->right = helper(pre, preL + 1 + (idx - postL) + 1, preR, post, idx + 1, postR - 1, m);
    return node;
}
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) { // time: O(n); space: O(n)
    // record the corresponding index of numbers in post-order traversal
    unordered_map<int, int> m;
    for (int i = 0; i < post.size(); ++i) m[post[i]] = i;
    return helper(pre, 0, pre.size() - 1, post, 0, post.size() - 1, m);
}

// Iteration
TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) { // time: O(n); space: O(n)
    vector<TreeNode*> st;
    st.push_back(new TreeNode(pre[0]));
    for (int i = 1, j = 0; i < pre.size(); ++i) {
        TreeNode* node = new TreeNode(pre[i]);
        while (st.back()->val == post[j]) {
            st.pop_back();
            ++j;
        }
        if (!st.back()->left) st.back()->left = node;
        else st.back()->right = node;
        st.push_back(node);
    }
    return st.front();
}