Rebuild a tree from preorder and inorder
A traversal lists every value of a binary tree in a fixed order. A subtree is a node together with everything below it. Two traversals matter here:
- Preorder: the node, then its left subtree in preorder, then its right subtree in preorder. The root comes first.
- Inorder: the left subtree in inorder, then the node, then the right subtree in inorder. Everything in the left subtree comes before the root, and everything in the right subtree comes after it.
You get both traversals of one tree, as the lists preorder and inorder. No value appears twice. Rebuild the tree out of TreeNode objects and return its root.
The tests compare trees with tree_values, which writes a tree in level order, the way build_tree reads it: the root, then each row from left to right, with None where a child is missing, and with any Nones at the end left off. The outputs below use that format.
preorder = [4, 9, 1, 6, 3], inorder = [9, 4, 6, 1, 3]Output[4, 9, 1, None, None, 6, 3]The root is 4, first in preorder. In inorder only 9 is left of the 4, so 9 is the left subtree. The right subtree's values come in preorder as 1, 6, 3, so 1 is its root. Inorder lists them as 6, 1, 3, so 6 hangs on the left of the 1 and 3 on its right.
preorder = [7], inorder = [7]Output[7]A single node.
preorder = [3, 2, 1], inorder = [1, 2, 3]Output[3, 2, None, 1]Each root is the last value of its part of inorder, so everything hangs to the left: 3, then 2 as its left child, then 1 as the left child of 2.
1 ≤ len(preorder) = len(inorder) ≤ 5 × 104
The values are distinct integers.
Both lists describe the same tree.
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.