LeetCode Solutions
    Reconstructing Binary Trees from Traversal Sequences

    Reconstructing Binary Trees from Traversal Sequences

    The problem asks us to reconstruct a binary tree from two given traversal sequences of that tree.

    Three Tree Traversals

    1. Preorder: Root - Left - Right
    2. Inorder: Left - Root - Right
    3. Postorder: Left - Right - Root

    The Approach

    We use divide-and-conquer based on the traversal patterns:

    Preorder: (Root) (Left subtree …) (Right subtree …) Inorder: (Left subtree …) (Root) (Right subtree …) Postorder: (Left subtree …) (Right subtree …) (Root)

    One sequence always gives us the root immediately. Once we have the root, we split the other sequence into left and right subtree parts. Then we recurse.

    For example: Preorder + Inorder

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    return createTree(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
}

TreeNode* createTree(vector<int>& preorder, vector<int>& inorder, int ps, int pe, int is, int ie) {
    if (ps > pe || is > ie) return NULL;
    // Find root in preorder
    int rootVal = preorder[ps];
    int idx;
    // Find split point in inorder using root value
    for(idx=is;idx<=ie&&inorder[idx]!=rootVal;++idx) {}

    TreeNode* troot = new TreeNode(rootVal);

    // Recursively build left subtree
    troot->left = createTree(preorder, inorder, ps+1, idx-is+ps, is, idx-1);
    // Recursively build right subtree
    troot->right = createTree(preorder, inorder, pe-(ie-idx)+1, pe, idx+1, ie);
    return troot;
}

    Inorder + Postorder works the same way. Find the root, then split the inorder sequence. Use element counts to split the postorder sequence for recursion.

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    return createTree(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
}

TreeNode* createTree(vector<int>& inorder, vector<int>& postorder, int is, int ie, int ps, int pe) {
    if (is > ie || ps > pe) return NULL;
    int rootVal = postorder[pe];
    int idx;
    for(idx=is;idx<=ie&&inorder[idx]!=rootVal;++idx) {}

    TreeNode* troot = new TreeNode(rootVal);
    troot->left = createTree(inorder, postorder, is, idx-1, ps, ps+idx-is-1);
    troot->right = createTree(inorder, postorder, idx+1, ie, ps+idx-is, pe-1);
    return troot;
}

    Preorder + Postorder both give us roots, but the splitting needs more care. We take the next element after the root in preorder and find its position in postorder. Then we split both sequences by matching lengths, following the same logic as before.

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

    TreeNode* createTree(vector<int>& pre, vector<int>& post, int pre_st, int pre_e, int po_st, int po_e) {
        if (pre_st > pre_e || po_st > po_e) return NULL;
        TreeNode* troot = new TreeNode(pre[pre_st]);
        // Base case: return when only root remains
        if (pre_st == pre_e) return troot;
        int post_idx=m[pre[pre_st+1]];
        
        troot->left = createTree(pre, post, pre_st+1, pre_st+1+post_idx-po_st, po_st, post_idx);
        troot->right = createTree(pre, post, pre_st+2+post_idx-po_st, pre_e, post_idx+1, po_e-1);
        return troot;
    }
    unordered_map<int, int> m;
};

    #recursion #divide-and-conquer #tree

    Queries on a Permutation With KeyRegular Expression Matching Demystified