A binary tree with distinct values was saved as two lists, and the tree itself was lost:
preorderlists every node before its left subtree, and the left subtree before the right subtree.inorderlists every node's left subtree, then the node, then its right subtree.
TreeNode(val, left=None, right=None) is in the starter. Keep it.
Write rebuild_tree(preorder, inorder) -> TreeNode: rebuild the tree and return its root. The two listings always describe exactly one tree. Empty lists mean an empty tree (None).
rebuild_tree([7, 3, 1, 5, 9, 8], [1, 3, 5, 7, 8, 9])
# 7
# / \
# 3 9
# / \ /
# 1 5 8
rebuild_tree([], []) # None
- Up to 20,000 nodes; values are distinct integers between
-10^9and10^9. - A tree can be as deep as it has nodes. If you recurse, raise the limit first (
sys.setrecursionlimit(50_000)), or build with an explicit stack. - ⭐ Bonus: a speed test on a 12,000-node chain earns a star in O(n). Scanning
inorderfor every subtree's root, or slicing the lists at every step, is O(n²) there.
Show hint
The first value of preorder is the root, and its position in inorder tells you how many values belong to the left subtree. Look positions up in a dictionary built once, and pass index ranges instead of slices.