leetcode/105-construct-binary-tree-from-preorder-and-inorder-traversal.py at master · anantkaushik/leetcode · GitHub

Name: leetcode/105-construct-binary-tree-from-preorder-and-inorder-traversal.py at master · anantkaushik/leetcode · GitHub
Rating: 4.8 (252 reviews)
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
"""
Problem Link: 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.

For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:
 3
 / \
 9 20
 / \
 15 7
"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
classSolution:
defbuildTree(self, preorder: List[int], inorder: List[int]) ->TreeNode:
ifnotpreorder:
return

inorder_indexes= {v:ifori, vinenumerate(inorder)}

preorder_index=1
root=TreeNode(preorder[0])
stack= [[root, 0, len(preorder)-1]]

whilepreorder_index<len(preorder):

node, start, end=stack[-1]
node_inorder_index=inorder_indexes[node.val]
cur_val=preorder[preorder_index]
cur_inorder_index=inorder_indexes[cur_val]

ifstart<=cur_inorder_index<=end:
new_node=TreeNode(cur_val)

ifcur_inorder_index<node_inorder_index:
node.left=new_node
stack.append([new_node, start, node_inorder_index-1])
else:
node.right=new_node
stack.append([new_node, node_inorder_index+1, end])
preorder_index+=1
else:
stack.pop()

returnroot

classSolution1:
defbuildTree(self, preorder: List[int], inorder: List[int]) ->TreeNode:
ifnotpreorder:
return

self.index=0
defhelper(start=0, end=len(inorder)-1):
ifstart>end:
return

root_val=preorder[self.index]
inorder_index=find_index(root_val, start, end)
ifinorder_index==-1:
return
else:
self.index+=1

node=TreeNode(root_val)
node.left=helper(start, inorder_index-1)
node.right=helper(inorder_index+1, end)

returnnode

deffind_index(root_val, start, end):
foriinrange(start, end+1):
ifinorder[i] ==root_val:
returni
return-1

returnhelper()

classSolution2:
defbuildTree(self, preorder: List[int], inorder: List[int]) ->TreeNode:
ifnotpreorder:
return

self.index=0
defhelper(order):
ifnotorder:
return
root_val=preorder[self.index]
inorder_index=find_index(order, root_val)
ifinorder_index==-1:
return
else:
self.index+=1

node=TreeNode(root_val)
node.left=helper(order[:inorder_index])
node.right=helper(order[inorder_index+1:])

returnnode

deffind_index(arr, val):
foriinrange(len(arr)):
ifarr[i] ==val:
returni
return-1

returnhelper(inorder)