Construct Binary Tree from Preorder and Inorder Traversal
Medium · tree dfs
A binary tree has been walked in two different ways and the values were written down each time.
preorderlists a node's value first, then everything in its left subtree, then everything in its right subtree (the same rule is applied inside every subtree).inorderlists everything in a node's left subtree first, then the node's own value, then everything in its right subtree.
All values in the tree are distinct. Rebuild the tree from the two lists and return its root. Both lists describe the same tree, so exactly one tree fits.
Examples
Example 1
Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: [3, 9, 20, null, null, 15, 7]
3 comes first in the preorder, so it is the root. 9 is the only value to its left in the inorder list, and 20, 15, 7 are to its right.
Example 2
Input: preorder = [-1], inorder = [-1]
Output: [-1]
A single value is a tree with one node.
Example 3
Input: preorder = [1, 2, 3], inorder = [3, 2, 1]
Output: [1, 2, null, 3]
Every value sits to the left of the one before it, so the tree is a chain running down to the left.
Constraints
- 1 <= len(preorder) <= 500
- len(inorder) == len(preorder)
- -3000 <= preorder[i], inorder[i] <= 3000
- All values in preorder are distinct.
- inorder is a permutation of preorder, and the two lists describe the same binary tree.