Build Binary Tree from Preorder and Inorder Traversal
Examples
Example 1:
Input: preorder = [1,2,3,4], inorder = [2,1,3,4]
Output: [1,2,3,null,null,null,4]
Example 2:
Input: preorder = [1], inorder = [1]
Output: [1]
Example 1:
Input: preorder = [1,2,3,4], inorder = [2,1,3,4]
Output: [1,2,3,null,null,null,4]
Example 2:
Input: preorder = [1], inorder = [1]
Output: [1]
You are given two integer arrays preorder and inorder.
preorder is the preorder traversal of a binary treeinorder is the inorder traversal of the same treeRebuild the binary tree from the preorder and inorder traversals and return its root.
1 <= inorder.length <= 1000inorder.length == preorder.length-1000 <= preorder[i], inorder[i] <= 1000Use recursion with indices and a hash map from value to its index in inorder. The first element of the current preorder slice is the root. The number of nodes in the left subtree is determined by the root's index in inorder. Recursively build left and right subtrees using the corresponding slices.
Preorder always lists the root first, while inorder splits the tree into left and right subtrees around the root. Using the inorder index lets us determine the exact subtree sizes, so the recursive reconstruction mirrors the original tree structure.
O(n)O(n)class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
index_map = {value: i for i, value in enumerate(inorder)}
pre_index = 0
def helper(left: int, right: int) -> Optional[TreeNode]:
nonlocal pre_index
if left > right:
return None
root_val = preorder[pre_index]
pre_index += 1
root = TreeNode(root_val)
mid = index_map[root_val]
root.left = helper(left, mid - 1)
root.right = helper(mid + 1, right)
return root
return helper(0, len(inorder) - 1)