Construct Binary Tree from Inorder and Postorder
Medium · Trees · Array · Hash Table · Divide and Conquer · Tree · Binary Tree
Problem
You are given two integer arrays, inorder and postorder, which are the inorder and postorder traversals of the same binary tree. All values are unique.
Rebuild the tree and return its root. The answer is shown in level order, with null for a missing child.
Examples
Input: inorder = [4,2,5,1,6,3], postorder = [4,5,2,6,3,1] Output: [1,2,3,4,5,6]
The last postorder value, 1, is the root; it splits inorder into [4,2,5] and [6,3].
Input: inorder = [2,7], postorder = [7,2] Output: [2,null,7]
2 is the root and 7 lies to its right in the inorder list.
Input: inorder = [9,3], postorder = [9,3] Output: [3,9]
3 is the root and 9 lies to its left in the inorder list.
Constraints
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- Values are unique and both arrays contain the same set of values
- The input is guaranteed to be a valid pair of traversals
Approaches
- Baseline: search and slice — time O(n^2), space O(n^2)
Follow-up
Inorder is what makes the split possible: preorder and postorder alone cannot tell a lone left child from a lone right child. The use cases write the preorder directly and measure the height, both without creating a node.
Related problems
Start free on Cariara · Coding problems · System design studio
