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.
Hint 1
Hint 2
- Inorder: Left ? Root ? Right
Hint 3
- Postorder: Left ? Right ? Root
- 0 = Number of nodes = 3000
- -10? = Node.data = 10?
- inorder and postorder consist of unique values
- Each value in postorder also appears in inorder
Unlock the code editor
Sign in to write, run, and submit your solution against the full test suite.
- Run code against sample & hidden test cases
- Save submissions and track your streak
- Compare with editorial & community solutions