Reconstruct Tree from Preorder and Postorder Sequences

You are given two integer arrays representing two different traversal sequences of the same binary tree containing distinct node values:

• preorder: This array captures the result of visiting nodes in a root-first manner — the root is visited before its left and right subtrees are explored recursively.
• postorder: This array captures the result of visiting nodes in a root-last manner — the left and right subtrees are explored recursively before the root is visited.

Your task is to reconstruct the original binary tree using only these two traversal sequences and return its root node.

Understanding the Traversal Orders

In a preorder traversal, we visit:

1. The current node (root)
2. All nodes in the left subtree (recursively in preorder)
3. All nodes in the right subtree (recursively in preorder)

In a postorder traversal, we visit:

1. All nodes in the left subtree (recursively in postorder)
2. All nodes in the right subtree (recursively in postorder)
3. The current node (root)

Key Insight

Unlike reconstruction from preorder + inorder (or postorder + inorder), reconstructing from preorder + postorder can yield multiple valid trees when nodes have only one child. This is because a single child could be either a left child or a right child — both interpretations produce the same preorder and postorder sequences.

In such ambiguous cases, you may return any valid binary tree that produces the given traversal sequences.

Output Format

Return the root of the reconstructed binary tree. The tree will be verified by performing a level-order traversal and comparing the node values.