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. - Aim for O(n). Scanning
inorderfor the root of every subtree, or copying slices of the lists at every step, is O(n²) on a lopsided tree.
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.