Core Traversal Definitions

• Pre-order: Process the root node, traverse the left subtree, then traverse the right subtree.
• In-order: Traverse the left subtree, process the root node, then traverse the right subtree.
• Post-order: Traverse the left subtree, traverse the right subtree, then process the root node.

Building from Pre-order and In-order Sequences

The initial element in the pre-order sequence always represents the current root. By locating this root value within the in-order sequence, the array is partitioned into left and right subtrees. The number of elements in the left partition dictates the boundary indices for the subsequent recursive calls. Recursion terminates when the starting index surpasses the ending index, indicating an empty subtree.

class Solution {
private:
    std::unordered_map<int, int> inOrderIdxMap;
    TreeNode* constructTree(const vector<int>& pre, const vector<int>& in, int pStart, int pEnd, int iStart, int iEnd) {
        if (pStart > pEnd) return nullptr;
        TreeNode* node = new TreeNode(pre[pStart]);
        int rootPos = inOrderIdxMap[pre[pStart]];
        int leftNodes = rootPos - iStart;
        node->left = constructTree(pre, in, pStart + 1, pStart + leftNodes, iStart, rootPos - 1);
        node->right = constructTree(pre, in, pStart + leftNodes + 1, pEnd, rootPos + 1, iEnd);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (int i = 0; i < inorder.size(); ++i) inOrderIdxMap[inorder[i]] = i;
        return constructTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
};

Building from In-order and Post-order Sequences

The final element in the post-order sequence serves as the root of the current subtree. Pinpointing this value in the in-order sequence separates the left and right subtrees. The size of the left subtree determines the slicing boundaries for the next recursive steps. The recursion halts when the valid range is exhausted.

class Solution {
private:
    std::unordered_map<int, int> inOrderIdxMap;
    TreeNode* constructTree(const vector<int>& in, const vector<int>& post, int iStart, int iEnd, int pStart, int pEnd) {
        if (iStart > iEnd) return nullptr;
        TreeNode* node = new TreeNode(post[pEnd]);
        int rootPos = inOrderIdxMap[post[pEnd]];
        int leftNodes = rootPos - iStart;
        node->left = constructTree(in, post, iStart, rootPos - 1, pStart, pStart + leftNodes - 1);
        node->right = constructTree(in, post, rootPos + 1, iEnd, pStart + leftNodes, pEnd - 1);
        return node;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        for (int i = 0; i < inorder.size(); ++i) inOrderIdxMap[inorder[i]] = i;
        return constructTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
};

Building from Pre-order and Post-order Sequences

Constructing a unique binary tree from pre-order and post-order traversals is generally impossible unless the tree is strictly binary. To generate one valid tree, the second element of the pre-order sequence is identified as the root of the left subtree. By finding this left-root value in the post-order sequence, the boundary between the left and right subtrees is established. Elements up to and including this position belong to the left subtree, while the remaining elements (excluding the final root) form the right subtree. The base case must explicitly handle single-node ranges.

class Solution {
private:
    std::unordered_map<int, int> postOrderIdxMap;
    TreeNode* constructTree(const vector<int>& pre, const vector<int>& post, int preS, int preE, int postS, int postE) {
        if (preS > preE) return nullptr;
        TreeNode* node = new TreeNode(pre[preS]);
        if (preS == preE) return node;
        int leftRootPos = postOrderIdxMap[pre[preS + 1]];
        int leftNodes = leftRootPos - postS + 1;
        node->left = constructTree(pre, post, preS + 1, preS + leftNodes, postS, leftRootPos);
        node->right = constructTree(pre, post, preS + leftNodes + 1, preE, leftRootPos + 1, postE - 1);
        return node;
    }
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        for (int i = 0; i < postorder.size(); ++i) postOrderIdxMap[postorder[i]] = i;
        return constructTree(preorder, postorder, 0, preorder.size() - 1, 0, postorder.size() - 1);
    }
};