105. Construct Binary Tree from Preorder and Inorder Traversal

Solution 1: Recursive

class Solution:
    def dfs(self, listPreOrd, listInOrd, idxPreStart, idxPreEnd, idxInStart, idxInEnd):
        if idxPreStart > idxPreEnd or idxInStart > idxInEnd:
            return None
        
        # Linear search to locate the root node
        rootOfBinaryTree = TreeNode(listPreOrd[idxPreStart])
        idxOfRoot = listInOrd.index(listPreOrd[idxPreStart], idxInStart, idxInEnd + 1)
        
        # Split left subtree
        lenOfLftTree = idxOfRoot - idxInStart
        lftSubTree = self.dfs(listPreOrd, listInOrd, 
                              idxPreStart + 1, idxPreStart + lenOfLftTree, 
                              idxInStart, idxInStart + lenOfLftTree - 1)
        # Split right subtree
        lenOfRhtTree = idxInEnd - idxOfRoot
        RhtSubTree = self.dfs(listPreOrd, listInOrd, 
                              idxPreStart + lenOfLftTree + 1, idxPreEnd, 
                              idxOfRoot + 1, idxInEnd)
        
        # Combine and return the rebuild result
        rootOfBinaryTree.left = lftSubTree
        rootOfBinaryTree.right = RhtSubTree
        return rootOfBinaryTree
    
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        idxPreStart, idxPreEnd = 0, len(preorder) - 1
        idxInStart, idxInEnd = 0, len(inorder) - 1
        rootOfBinaryTree = self.dfs(preorder, inorder, idxPreStart, idxPreEnd, idxInStart, idxInEnd)
        return rootOfBinaryTree

Time Complexity: O(N)
Space Complexity: O(N) // Recursive call stack

Solution 2: Recursive + Hash (Optimized)

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

Reference

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/34538/My-Accepted-Java-Solution