Leetcode 105: Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/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.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root
        

 

Idea

The root of a preorder list is always `preorder[0]`. You need to find the index of the root in inorder list. After that, you can divide the problem into two smaller problems.

 

I used to use a more memory consuming version (using a lot of slicing). This version ended up with Memory Limit Exceeded exception. Therefore, we should avoid using slicing as much as possible. (See my another post talking about slicing in python: https://czxttkl.com/?p=1353)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        root = self.work(preorder, inorder)
        return root
    
    def work(self, preorder, inorder):
        assert len(preorder) == len(inorder)
        if len(preorder) == 0:
            return None
            
        root = TreeNode(preorder[0])
        for idx, num in enumerate(inorder):
            if num == root.val:
                root.left = self.work(preorder[1:idx+1], inorder[:idx])
                root.right = self.work(preorder[idx+1:], inorder[idx+1:])
        return root