Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.
If there exist multiple answers, you can return any of them.
Example 1:
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]
Example 2:
Input: preorder = [1], postorder = [1] Output: [1]
Constraints:
1 <= preorder.length <= 301 <= preorder[i] <= preorder.lengthpreorder are unique.postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthpostorder are unique.preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.This approach involves recursively dividing the preorder and postorder arrays to construct the tree. The first element of the preorder array is the root of the tree. The left subtree can be determined by identifying the position of the second element in preorder in the postorder array. Recursively apply this strategy for each subtree.
This solution defines the TreeNode class and implements a recursive method constructFromPrePost. The method splits the preorder and postorder lists to find left and right subtrees, creating TreeNode objects recursively. The base case checks for empty lists, indicating no subtree exists, thus returning None.
C++
Java
C#
JavaScript
Time Complexity: O(n^2) - Each split requires a scan operation which can take O(n) time. The recursion might stack as many times as there are elements, making this approach potentially expensive.
Space Complexity: O(n) - Due to the recursion stack and additional space required for the tree nodes.
This method optimizes the naive recursive approach by using a hash map to store the indices of values in the postorder sequence. By doing so, we can quickly find the index of the next root node, reducing the time complexity significantly. This way, the subtrees can be constructed in a more efficient manner by avoiding repeated searches.
The optimized Python approach uses a hash map to store the values and their indices in the postorder sequence. This allows for O(1) time complexity for querying indices in the postorder array. The recursive construct method builds the tree using the preIndex to track root values in preorder.
C++
Java
C#
JavaScript
Time Complexity: O(n) - Hash map optimization reduces the search time significantly.
Space Complexity: O(n) - Due to the hash map and recursion stack.
| Approach | Complexity |
|---|---|
| Recursive Construction by Dividing Preorder and Postorder Arrays | Time Complexity: O(n^2) - Each split requires a scan operation which can take O(n) time. The recursion might stack as many times as there are elements, making this approach potentially expensive. Space Complexity: O(n) - Due to the recursion stack and additional space required for the tree nodes. |
| Recursive Approach with Hash Map Optimization | Time Complexity: O(n) - Hash map optimization reduces the search time significantly. Space Complexity: O(n) - Due to the hash map and recursion stack. |
5.9 Construct Binary Tree from Preorder and Postorder traversal | Data Structure Tutorials • Jenny's Lectures CS IT • 785,192 views views
Watch 9 more video solutions →Practice Construct Binary Tree from Preorder and Postorder Traversal with our built-in code editor and test cases.
Practice on FleetCode