Tree Traversal Target: 15s
Preorder[0] is root. Find root in inorder → left subtree is inorder[:mid], right is inorder[mid+1:].
def buildTree(preorder, inorder):
if not preorder: return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = buildTree(preorder[1:mid+1], inorder[:mid])
root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
return root
# Optimized: use hashmap for O(1) index lookup
def buildTree_opt(preorder, inorder):
idx = {v: i for i, v in enumerate(inorder)}
it = iter(preorder)
def build(lo, hi):
if lo > hi: return None
val = next(it)
node = TreeNode(val)
mid = idx[val]
node.left = build(lo, mid - 1)
node.right = build(mid + 1, hi)
return node
return build(0, len(inorder) - 1)Type it from memory. Go.