leetcode

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

Recursive Version - 148ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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 inorder:
            idx = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[idx])
            root.left = self.buildTree(preorder, inorder[0:idx])
            root.right = self.buildTree(preorder, inorder[idx+1:])
            return root

test code

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
In [39]: class TreeNode:
    ...:     def __init__(self, x):
    ...:         self.val = x
    ...:         self.left = None
    ...:         self.right = None
In [50]: # 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 inorder:
    ...:             idx = inorder.index(preorder.pop(0))
    ...:             root = TreeNode(inorder[idx])
    ...:             root.left = self.buildTree(preorder, inorder[0:idx])
    ...:             root.right = self.buildTree(preorder, inorder[idx+1:])
    ...:             return root
    
In [52]: pre_o = [3,9,20,15,7]
In [53]: in_o = [9,3,15,20,7]
In [54]: s = Solution(); t = s.buildTree(pre_o, in_o); print(t)
<__main__.TreeNode object at 0x10d8128d0>
In [55]: t.right.val
Out[55]: 20
In [56]: t.right.left.val
Out[56]: 15
In [57]: t.right.right.val
Out[57]: 7

leet code