Construct Tree from Inorder + Postorder
You are given two integer arrays, inorder and postorder, representing the inorder and postorder traversals of a binary tree.
Your task is to reconstruct and return the original binary tree.
Since all node values are unique, the binary tree can be reconstructed uniquely from the given traversals.
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Explanation: The last element of postorder (3) is the root; splitting inorder around it reconstructs the left and right subtrees recursively.
Input: inorder = [1], postorder = [1]
Output: [1]
Explanation: A single value reconstructs a single-node tree.
Input: inorder = [], postorder = []
Output: []
Explanation: Empty traversals produce an empty tree.
- 0 = Number of nodes = 3000
- -10? = Node.data = 10?
- inorder and postorder consist of unique values
- Each value in postorder also appears in inorder
- The traversals follow these orders:
- Inorder: Left ? Root ? Right
- Postorder: Left ? Right ? Root
See how the best solutions work
Approach, complexity and clean code in every language. Sign in to unlock the editorial.
Keep every attempt
Your submissions, results and runtime history live here. Sign in to start your streak.
4 2 5 1 6 3 7 4 5 2 6 7 3 1
1 2 3 4 5 6 7
2 5 7 10 12 15 20 2 7 5 12 20 15 10
10 5 15 2 7 12 20