Problem Informations

• Problem Index: 889
• Problem Link: Construct Binary Tree from Preorder and Postorder Traversal
• Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Problem Description

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

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 \leq \text{preorder.length} \leq 30$
• $1 \leq \text{preorder}[i] \leq \text{preorder.length}$
• All the values of preorder are unique.
• $\text{postorder.length} == \text{preorder.length}$
• $1 \leq \text{postorder}[i] \leq \text{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.

Intuition

To reconstruct the binary tree from its preorder and postorder traversals, we need to understand the properties of these traversal methods. The preorder traversal provides us with the root nodes in top-down order, whereas the postorder traversal gives us the root nodes in bottom-up order. Given these characteristics, we can use the fact that the first element in the preorder traversal is the root of the tree, and the last element in the postorder traversal is also the root of the tree.

By leveraging the distinction between how subtrees are represented in both traversals, we can recursively split the traversals into segments that represent the left and right subtrees.

Approach

1. Check Base Cases: Begin by checking if the preorder list is empty. If it is, there is no tree to reconstruct, so we return nullptr.

2. Identify the Root: The first element of the preorder array is always the root of the current subtree being constructed. Therefore, create a TreeNode with this value.

3. Single Node Case: If the size of the preorder list is one, it indicates that we are dealing with a single-node tree. In this case, we return the created root node.

4. Determine Subtree Boundaries: The second element in the preorder list is the root of the left subtree. In the postorder list, the left subtree elements appear before the right subtree and the root of the subtrees. To find the boundary indices for left and right subtrees:

   • Find the position of the element at postorder[postorder.size() - 2] in the preorder list. This index tells us where the division between left and right subtrees occurs in the preorder list.

5. Recursive Tree Construction:

   • Left Subtree Construction: Recursively call the constructFromPrePost function using the preorder elements that represent the left subtree and relevant postorder elements.
   • Right Subtree Construction: Similarly, recursively call the constructFromPrePost function for the right subtree using their respective preorder and postorder segments.

6. Return the Root: After constructing both left and right subtrees, attach them to the root node’s left and right pointers, respectively, and then return the root node.

This approach effectively utilizes the properties of the preorder and postorder sequences, splitting them into appropriate sections that allow for accurate reconstruction of the binary tree.

Code

C++

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* constructFromPrePost(vector<int> preorder, vector<int> postorder) {
        // If the preorder list is empty, there's no tree to construct
        if (preorder.empty()) {
            return nullptr;
        }
        
        // The first element in preorder is the root of the tree
        TreeNode* root = new TreeNode(preorder[0]);
        
        // If there's only one element, it's a single-node tree
        if (preorder.size() == 1) {
            return root;
        }

        // Find the index at which we split the preorder list into left and right subtrees
        int splitIndex = find(preorder.begin(), preorder.end(), postorder[postorder.size() - 2]) - preorder.begin();

        // Recursive construction of the left subtree
        root->left = constructFromPrePost(
            vector<int>(preorder.begin() + 1, preorder.begin() + splitIndex), 
            vector<int>(postorder.begin(), postorder.begin() + splitIndex - 1)
        );

        // Recursive construction of the right subtree
        root->right = constructFromPrePost(
            vector<int>(preorder.begin() + splitIndex, preorder.end()),
            vector<int>(postorder.begin() + splitIndex - 1, postorder.end() - 1)
        );

        return root;
    }
};

Python

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right
        
class Solution:
    def constructFromPrePost(self, preorder, postorder):
        # If the preorder list is empty, there's no tree to construct
        if not preorder:
            return None
        
        # The first element in preorder is the root of the tree
        root = TreeNode(preorder[0])
        
        # If there's only one element, it's a single-node tree
        if len(preorder) == 1:
            return root

        # Find the index at which we split the preorder list into left and right subtrees
        splitIndex = preorder.index(postorder[-2])

        # Recursive construction of the left subtree
        root.left = self.constructFromPrePost(
            preorder[1:splitIndex], 
            postorder[:splitIndex - 1]
        )

        # Recursive construction of the right subtree
        root.right = self.constructFromPrePost(
            preorder[splitIndex:],
            postorder[splitIndex - 1:-1]
        )

        return root

Complexity

• Time complexity: $O(n^2)$

  The time complexity is $O(n^2)$ because, for each recursive call, the program uses find to locate the position of the next root node in the preorder list, which takes $O(n)$ time. The function is called recursively for each subtree, and in the worst case, this results in $n$ recursive calls, with each call requiring $O(n)$ operations to find the split index, leading to an overall complexity of $O(n^2)$.

• Space complexity: $O(n^2)$

  The space complexity is $O(n^2)$ due to the creation of new vectors in each recursive call. At each level of recursion, two new vectors are created by slicing the preorder and postorder arrays, each contributing to the space usage. In the worst case, these operations result in a quadratic space complexity since you have depth $O(n)$ and at each depth, you’re potentially storing $O(n)$ elements.