LeetCode Solutions Blog

Construct Binary Tree from Preorder and Postorder Traversal

Number: 925

Difficulty: Medium

Paid? No

Problem Description

Given two integer arrays, preorder and postorder, representing the preorder traversal and postorder traversal of a binary tree with distinct values, reconstruct and return the binary tree. If there are multiple possible trees, return any one of them.

Key Insights

The first element in the preorder traversal is always the root of the tree.
The next element in preorder is the root of the left subtree.
Locate the left subtree’s root in the postorder traversal to determine the size of the left subtree.
Recursively construct the left and right subtrees using the calculated boundaries.

Space and Time Complexity

Time Complexity: O(n) on average when using a hashmap to quickly locate indices in postorder, but can be O(n^2) in the worst-case without optimization. Space Complexity: O(n) due to recursion and storage of indices in a hashmap.

Solution

We use a recursive approach. The first element of preorder determines the root. If the tree has only one node, we return immediately. Otherwise, we determine the size of the left subtree by finding the index of preorder[1] in the postorder array. This size helps split the preorder and postorder arrays into segments representing the left and right subtrees. Then, we recursively construct the subtrees. To reduce time complexity, a hashmap (or dictionary) is used to store the indices of elements from the postorder traversal so the index lookup is O(1).

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def constructFromPrePost(self, preorder: list[int], postorder: list[int]) -> TreeNode:
        # Build a hashmap for quick lookup of index positions in postorder traversal
        post_index = {value: idx for idx, value in enumerate(postorder)}

        def helper(pre_start, pre_end, post_start, post_end):
            # Base condition: if there are no elements to construct the tree.
            if pre_start > pre_end:
                return None
            # The first element in the current preorder segment is the root.
            root = TreeNode(preorder[pre_start])
            # If only one element, it's a leaf node.
            if pre_start == pre_end:
                return root
            # The next element in preorder is the left subtree's root.
            left_root_val = preorder[pre_start + 1]
            # Find out the boundary in postorder for the left subtree.
            left_subtree_idx = post_index[left_root_val]
            # Calculate the number of elements in the left subtree.
            left_size = left_subtree_idx - post_start + 1

            # Recursively build the left and right subtrees.
            root.left = helper(pre_start + 1, pre_start + left_size, post_start, left_subtree_idx)
            root.right = helper(pre_start + left_size + 1, pre_end, left_subtree_idx + 1, post_end - 1)
            return root

        return helper(0, len(preorder) - 1, 0, len(postorder) - 1)