105. Construct Binary Tree from Preorder and Inorder Traversal

Summary

Given two integer arrays preorder and inorder, where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Approach

Use recursion. We get the current root from preorder, and we get the left and right subtree ranges from inorder.

preorder visits nodes in this order: root, left, right.

inorder visits nodes in this order: left, root, right.

So in preorder, the first value is always the current root.

In inorder, we can find which nodes belong to the left subtree and which belong to the right subtree.

If the tree contains only right nodes, then:

preorder: [root, next right, next right, ...]
inorder: [root, right node, ...]

So when we build the tree, we pick the first root, and its left child must be None because there are no nodes to the left of the root in the inorder result.

Function

Initialization:

inorder_num2idx = {}, where the key is a number in the inorder result and the value is its index.
pre_idx = 0

Function build(in_left, in_right): nonlocal pre_idx If in_left > in_right: return None root_val = preorder[pre_idx] pre_idx += 1 root = TreeNode(root_val) mid = inorder_num2idx[root_val] root.left = build(in_left, mid - 1) root.right = build(mid + 1, in_right) return root

Return build(0, len(inorder) - 1).

Complexity

Time Complexity: O(N) Space Complexity: O(N)