Construct Binary Tree from Preorder and Inorder Traversal

Intuition

• Take advantage of the following facts:
  • Use the index

Speed Up

• You can use a hashmap instead of indexing
• You can use a set of prefix arrays or something of that regard to access the tree instead of computing the preorder and inorder every time (store the computation so that you don’t have to continually compute the same subarray).

Code

Sub-Optimal Solution

# 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 and inorder):
            return None
        node = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        node.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        node.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return node

Notes

---

References

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/