Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

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

Drawing a figure will make this more clear.
                    A
                   /   \
                 B    C
                /   \
              D    E
Preorder: ABDEC; inorder: DBEAC.

So the thing is pretty clear: first we get the root in preorder, namley A, the nodes before A in the inorder sequence is left subtree, after A is right subtree. For preorder to judge left and right subtree, just to count numbers: in inorder there are 3 left and 1 right, hence in preorder we take BDE the three as left tree and remaining part as right tree, then go recursion.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param preorder, a list of integers
    # @param inorder, a list of integers
    # @return a tree node
    def buildTree(self, preorder, inorder):
        lookup = {}
        for i, num in enumerate(inorder):
            lookup[num] = i
        return self.buildTreeRecu(lookup, preorder, inorder, 0, 0, len(inorder))
    
    def buildTreeRecu(self, lookup, preorder, inorder, pre_start, in_start, in_end):
        if in_start == in_end:
            return None
        node = TreeNode(preorder[pre_start])
        i = lookup[preorder[pre_start]]
        node.left = self.buildTreeRecu(lookup, preorder, inorder, pre_start + 1, in_start, i)
        node.right = self.buildTreeRecu(lookup, preorder, inorder, pre_start + 1 + i - in_start, i + 1, in_end)
        return node

Run Time: 88 ms