Given two lists of distinct integers, inorder and postorder, that are the inorder and postorder traversals of the same binary tree, rebuild that tree and return its root.
Examples
3
/ \
9 20
/ \
15 7
Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: tree_to_list(...) == [3, 9, 20, None, None, 15, 7]
Input: inorder = [2, 1], postorder = [2, 1]
Output: [1, 2]
Constraints
0 <= len(inorder) == len(postorder) <= 1000- All values are distinct and the two lists describe a valid tree
Goals
- Read the postorder sequence from the back to obtain roots
- Build the right subtree before the left when consuming postorder in reverse