Construct Binary Tree from Preorder and Postorder Traversal

This problem is a classical problem of tree construction based on traversal results.

Let’s break it down:

1. The first element of preorder is the root.
2. The last element of postorder is also the root.

Using these two pieces of information:

1. The second element of preorder would be the root of the left subtree (if it exists).
2. From postorder, we can find out where the left subtree ends because that’s where this root of the left subtree would be.

Given this information, we can divide the preorder and postorder into parts that represent the left and right subtrees and solve for them recursively.

Here’s how you can implement it:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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]) -> Optional[TreeNode]:
        if not preorder or not postorder:
            return None

        root = TreeNode(preorder[0])
        if len(preorder) == 1:
            return root

        leftRoot = preorder[1]
        idx = postorder.index(leftRoot)
        
        root.left = self.constructFromPrePost(preorder[1: idx+2], postorder[:idx+1])
        root.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])

        return root

With this approach, the tree is built in a recursive manner. The recursion breaks down the problem into smaller subproblems that are analogous to the original problem, making it an elegant and effective way to construct the tree from given order traversals.