Medium

Construct Binary Tree from Preorder and Inorder Traversal

LAB

Build the binary tree from preorder and inorder traversals and return its level-order encoding using -100000 for null gaps.

EXAMPLES

Example 1

Input
{
  "preorder": [
    3,
    9,
    20,
    15,
    7
  ],
  "inorder": [
    9,
    3,
    15,
    20,
    7
  ]
}

Output
[
  3,
  9,
  20,
  -100000,
  -100000,
  15,
  7
]

FUNCTION SHAPE

preorder: intArrayinorder: intArray→intArray

SOLUTION NOTE

Preorder = [root, L, R]. Inorder = [L, root, R]. The root is the first preorder element. Use inorder to find where left/right subtrees split. Build left subtree first (matches preorder).

Reveal reference solution +

pythonREFERENCE

def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    # Map value -> index in inorder
    inorder_idx = {v: i for i, v in enumerate(inorder)}
    preorder_index = 0

    def build(left, right):
        nonlocal preorder_index
        if left > right:
            return None

        # Root is next element in preorder
        root_val = preorder[preorder_index]
        root = TreeNode(root_val)
        preorder_index += 1

        # Split inorder array at root
        root.left = build(left, inorder_idx[root_val] - 1)
        root.right = build(inorder_idx[root_val] + 1, right)

        return root

    return build(0, len(preorder) - 1)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗