Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Solution:

The key point is to figure out the root for each recursion and also use python sub list [start:stop:step] to locate a range of preorder and inorder instead of indexing range.

    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if preorder == None or inorder == None or len(preorder) == 0 or len(inorder) == 0:
            return None
        root = TreeNode(preorder[0])
        i = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1 : i + 1], inorder[0:i])
        root.right = self.buildTree(preorder[i + 1: len(preorder)], inorder[i + 1 : len(inorder)])

        return root