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]

Input: preorder = [1], postorder = [1]
Output: [1]

Solution Explanation: Construct Binary Tree from Preorder and Postorder Traversal

This problem involves reconstructing a binary tree given its preorder and postorder traversals. Both solutions presented utilize recursion, leveraging the inherent properties of these traversal types.

Key Properties of Preorder and Postorder Traversal:

• Preorder: Root -> Left Subtree -> Right Subtree
• Postorder: Left Subtree -> Right Subtree -> Root

This means the root of the entire tree is always the first element in the preorder traversal and the last element in the postorder traversal. This forms the basis for the recursive approach.

Solution 1: Recursion with Hashmap

This solution employs a recursive helper function dfs and a hashmap pos.

Algorithm:

1. Hashmap Creation: A hashmap pos is created to store the index of each element in the postorder array. This allows for O(1) lookup time when searching for a node's position in the postorder traversal.

2. Recursive Function dfs(a, b, c, d):

   • a, b: Indices defining the range of the preorder traversal for the current subtree.
   • c, d: Indices defining the range of the postorder traversal for the current subtree.

   The function performs the following:

   • Base Case: If a > b (empty range), it returns null.
   • Root Node Creation: A TreeNode is created with the value preorder[a] (the root of the current subtree).
   • Base Case (Single Node): If a == b, the subtree consists of only the root node, so it's returned.
   • Left and Right Subtree Division:
     • The root of the left subtree is preorder[a + 1]. Its index in the postorder array (i) is found using the pos hashmap.
     • m represents the number of nodes in the left subtree.
     • The ranges for the left and right subtrees in both preorder and postorder are determined.
   • Recursive Calls: dfs is recursively called for the left and right subtrees using the calculated ranges.
   • Return Value: The root node of the constructed subtree is returned.

3. Main Function Call: The dfs function is initially called with the full ranges of the preorder and postorder arrays.

Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once during the recursive calls.

Space Complexity: O(n) due to the recursive call stack and the hashmap pos.

Solution 2: Recursive Approach without Hashmap

This solution also uses recursion but avoids using a hashmap. It achieves the same result by directly searching for the left subtree's root in the postorder traversal during each recursive call. This makes it slightly less efficient in terms of time complexity.

Algorithm:

The recursive function dfs(i, j, n) works similarly to Solution 1:

1. Base Cases: Handles empty ranges (n <= 0) and single-node subtrees (n == 1).
2. Root Node Creation: Creates a TreeNode with the value from the preorder traversal.
3. Left Subtree Search: It iterates through the postorder array to find the index k of the left subtree's root (preorder[i + 1]).
4. Subtree Division: The number of nodes in the left and right subtrees (m and n - m - 1) are determined.
5. Recursive Calls: Recursive calls are made for the left and right subtrees.
6. Return Value: Returns the constructed root node.

Time Complexity: O(n^2) in the worst case. The linear search within the postorder array in each recursive call contributes to the quadratic time complexity.

Space Complexity: O(n) due to the recursive call stack.

Code Examples (Python): The provided code snippets show implementations of both solutions in Python, as well as in other languages (Java, C++, Go, TypeScript). Solution 1 (with hashmap) is generally preferred due to its better time complexity.

In summary, both solutions effectively reconstruct the binary tree, but Solution 1 offers a significant performance advantage by using a hashmap for faster lookups. The choice between them depends on the specific constraints and performance requirements of the application.