Construct Binary Tree from Inorder and Postorder Traversal
Problem Description
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Constraints:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorderandpostorderconsist of unique values.- Each value of
postorderalso appears ininorder. inorderis guaranteed to be the inorder traversal of the tree.postorderis guaranteed to be the postorder traversal of the tree.
Solve it on LeetCode
Approaches
1. Recursive Solution
Intuition:
In a binary tree, the postorder traversal visits the left subtree, the right subtree, and the node itself. The last element in the postorder array is the root of the tree. For the inorder array, the left subtree is on its left, and the right subtree is on its right. We can recursively build the tree using these properties.
Explanation:
- The last element in the postorder traversal is always the root node.
- Find this root in the inorder array. The inorder array splits into left and right subtrees based on the root's position.
- Recursively build the left and right subtrees using the same logic.
Code:
- Time Complexity: O(n^2) – We might end up searching through the inorder list for the root multiple times.
- Space Complexity: O(n) – for the recursion stack.
2. Optimized Recursive Solution Using HashMap
Intuition:
To improve the efficiency of finding the root index in the inorder traversal, we can use a HashMap to store the indices of elements in the inorder array. This allows us to find the root index in O(1) time.
Explanation:
- HashMap is used to store the indices of each value in inorder traversal.
- We find the root element position from the map directly, reducing time complexity.
Code:
- Time Complexity: O(n) – Improved by using a map to get indices in constant time.
- Space Complexity: O(n) – for the hashmap and recursion stack.