LC 105 - Construct Binary Tree from Preorder and Inorder Traversal

Question

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.

Example 1:

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

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

Links

Question here and solution here

Solution

concept

The main idea here is to notice that:

1. first element of preorder is always the root
2. if we find the index of this root in inorder, then all the element before this index belongs to the left sub tree, and all element after this index belongs to the right subtree
3. we can directly use the index in inorder to partition preorder array

code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None

        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid]) # inorder[mid] is the root, it is skipped here
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])

        return root

Complexity

time: $O(n^2)$
space: $O(n)$