Construct Binary Tree from Preorder and Postorder Traversal

Problem Statement

In this problem, we are given two arrays representing the preorder and postorder traversals of a binary tree. The task is to reconstruct the original binary tree from these traversal sequences. It is essential to note that the values in both arrays are unique and belong distinctly to the nodes of the tree. You can potentially construct multiple valid binary trees from the given sequences, but only one needs to be returned as an output.

Examples

Example 1

Input:

preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]

Output:

[1,2,3,4,5,6,7]

Example 2

Input:

preorder = [1], postorder = [1]

Output:

[1]

Constraints

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• All the values of preorder are unique.
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• All the values of postorder are unique.
• It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Approach and Intuition

The reconstruction of a binary tree from its preorder and postorder traversals hinges on understanding these traversals' properties and how they define the structure of the tree. The root of the problem absorbs the fact that preorder traversal starts with the root node followed by the subtrees, while postorder traversal ends with the root after covering the subtrees. Here’s a structured approach to solve the problem:

1. Identify the root of the tree from the preorder array (it's always the first element).
2. Locate the roots of the left and right subtrees. The root of the left subtree in preorder will directly follow the main root. Similarly, in postorder, the root before the main root is the root of the right subtree.
3. Develop a recursive function that,
   • Takes corresponding sections of the preorder and postorder arrays that deal with a specific subtree.
   • Determines the roots and boundaries for the next level of recursion.
4. Continue splitting the tree into subtrees recursively until the entire tree is reconstructed.
5. If at any step, the corresponding subtrees' information contradicts (like non-alignment of array boundaries), you might need to revisit the slicing done based on roots found.

Example Elaborations from given examples:

• Example 1: Starting with 1 as the root from preorder, we locate the next elements to build the subtrees. The tree is continuously spliced following the rules derived from the preorder and postorder traces until all elements are correctly placed.
• Example 2: Being a single element array, the root is 1, and as there are no further elements, 1 itself is the entire tree.

The recursive military precision applied when building each subtree ensures every node is correctly placed, respecting their original relationships in the given tree, as reflected by its traversals.

Solutions

class Solution {
public:
    TreeNode* buildFromPrePost(vector<int>& pre, vector<int>& post) {
        int prePos = 0;
        int postPos = 0;
        return build(prePos, postPos, pre, post);
    }
    
private:
    TreeNode* build(int& prePos, int& postPos, vector<int>& pre, vector<int>& post) {
        TreeNode* node = new TreeNode(pre[prePos]);
        prePos++;
            
        if (node->val != post[postPos]) {
            node->left = build(prePos, postPos, pre, post);
        }
    
        if (node->val != post[postPos]) {
            node->right = build(prePos, postPos, pre, post);
        }
            
        postPos++;
            
        return node;
    }
};