LeetCode #105 Construct Binary Tree from Preorder and Inorder Traversal

Posted on | Post modified | In , , , , , , , , ,

Problem

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

Example

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Note

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

Solution1

Method: Divide and Conquer (recursive)

Time Complexity: O(n)

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder:
            return None
        if len(preorder) == 1:
            return TreeNode(preorder[0])
        else:
            root = TreeNode(preorder[0])
            partition = inorder.index(preorder[0])
            root.left = self.buildTree(preorder[1: 1 + partition], inorder[: partition])
            root.right = self.buildTree(preorder[1 + partition:], inorder[1 + partition:])
            
            return root

Solution2

Method: Divide and Conquer (Iterator and map)

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        
        inor_dict = {}
        for i, num in enumerate(inorder):
            inor_dict[num] = i
        pre_iter = iter(preorder)
        
        def helper(start, end):
            if start > end:return None
            root_val = next(pre_iter)
            root = TreeNode(root_val)
            idx = inor_dict[root_val]
            root.left = helper(start, idx-1)
            root.right = helper(idx+1, end)
            return root
        
        return helper(0, len(inorder) - 1)