-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
106.py
53 lines (49 loc) · 1.82 KB
/
106.py
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
__________________________________________________________________________________________________
sample 52 ms submission
# 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, inorder: List[int], postorder: List[int]) -> TreeNode:
index_map = {v:k for k,v in enumerate(inorder)}
R_postorder = postorder[::-1]
postorder_index = 0
def dfs(left,right):
if left == right:
return None
nonlocal postorder_index
val = R_postorder[postorder_index]
postorder_index += 1
root = TreeNode(val)
mid = index_map[val]
root.right = dfs(mid+1,right)
root.left = dfs(left,mid)
return root
return dfs(0,len(postorder))
__________________________________________________________________________________________________
sample 18116 kb submission
# 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, inorder: List[int], postorder: List[int]) -> TreeNode:
inorder_map = {}
for i, n in enumerate(inorder):
inorder_map[n] = i
def build(lo: int, hi: int) -> TreeNode:
if lo > hi:
return None
val = postorder.pop()
root = TreeNode(val)
pos = inorder_map[val]
root.right = build(pos + 1, hi)
root.left = build(lo, pos - 1)
return root
return build(0, len(inorder) - 1)
__________________________________________________________________________________________________