Construct Binary Tree from Inorder and Postorder Traversal
Medium · tree dfs
A binary tree was walked in two different ways, and the values were written down each time.
inorderlists everything in a node's left subtree first, then the node's own value, then everything in its right subtree.postorderlists everything in a node's left subtree first, then everything in its right subtree, and the node's own value last. The same rule applies inside every subtree.
All the values in the tree are distinct. Rebuild the tree from the two lists and return its root. Both lists describe the same tree, and exactly one tree fits them.
Examples
Example 1
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. In the inorder list 4, 2, 5 are to its left and 6, 3 to its right. The right part ends with 3 in postorder, so 3 is the right child, and 6 is left of it.
Example 2
Input: inorder = [8], postorder = [8]
Output: [8]
One value is a tree with a single node.
Example 3
Input: inorder = [1, 2, 3], postorder = [3, 2, 1]
Output: [1, null, 2, null, 3]
Nothing is to the left of 1 in the inorder list, and the same holds for 2, so the tree is a chain running down to the right.
Constraints
- 1 <= len(inorder) <= 500
- len(postorder) == len(inorder)
- -3000 <= inorder[i], postorder[i] <= 3000
- All values in inorder are distinct.
- postorder is a permutation of inorder, and the two lists describe the same binary tree.