889. Construct Binary Tree from Preorder and Postorder Traversal
Medium
30 Points
Array
Hash Table
Divide and Conquer
Tree
Binary Tree
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.
Examples
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.lengthAll the values of preorder are unique.postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthAll the values of postorder are unique.It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.
889. Construct Binary Tree from Preorder and Postorder Traversal
Medium
30 Points
Array
Hash Table
Divide and Conquer
Tree
Binary Tree
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.
Examples
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.lengthAll the values of preorder are unique.postorder.length == preorder.length1 <= postorder[i] <= postorder.lengthAll the values of postorder are unique.It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.