You are given two lists describing the same binary tree, whose values are all different:
preorderlists the values in preorder: a node, then its left subtree, then its right subtree.inorderlists them in inorder: a node's left subtree, then the node, then its right subtree.
Build the tree and return its root.
The answer is checked as the tree written in level order, row by row from the top, with null
where a node is missing: [4, 2, 7, null, 3] is 4 at the root, 2 and 7 below it, and 3 as the
right child of 2.
Example 1
- Input
- preorder = [5, 2, 1, 4, 8, 9], inorder = [1, 2, 4, 5, 8, 9]
- Output
- [5, 2, 8, 1, 4, null, 9]
Example 2
- Input
- preorder = [1, 2], inorder = [1, 2]
- Output
- [1, null, 2]
Constraints
- Both lists hold the same 1 to 1000 values.
- Values are distinct, between −3000 and 3000.
- The tree is at most 100 levels deep.
Show the pattern
Trees
The preorder's first value is the root, and finding the root in the inorder splits the rest into the left and right subtrees. Each side is a smaller copy of the same problem: recursion.
See trees in a visualiserShow the approach
The first value in preorder is the root. Its position in inorder splits the inorder into the
left subtree's values (before it) and the right subtree's (after it). In the preorder, the root
is followed by the whole left subtree and then the whole right subtree.
So build recursively over a stretch lo..hi of the inorder, reading the preorder from left to
right with one shared index. Take the next preorder value as this stretch's root and find its
inorder position m, using a hash map from value to position. Build the left subtree from
lo..m − 1, then the right subtree from m + 1..hi. An empty stretch is an empty subtree.
Building the left side before the right is what keeps the shared preorder index in step.
Time: O(n) · Space: O(n) for the map, plus O(h) for the recursion