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
| class Node:
def __init__(self, item):
self.item = item
self.left = None
self.right = None
self.parent = None
class BinaryTree():
def __init__(self):
self.root = None
cnt = 0
def solution(k, num, links):
answer = 0
tree = BinaryTree()
node_list = []
for i in range(len(num)):
node_list.append(Node(num[i]))
for i in range(len(links)):
if links[i][0] != -1:
node_list[i].left = node_list[links[i][0]]
node_list[i].left.parent = node_list[i]
if links[i][1] != -1:
node_list[i].right = node_list[links[i][1]]
node_list[i].right.parent = node_list[i]
for i in range(len(num)):
if node_list[i].parent == None:
tree.root = node_list[i]
left, right = 0, 10**9
global cnt
while left <= right:
mid = (left + right) // 2
cnt = 1
a = dfs(tree.root, mid)
if cnt <= k:
answer = mid
right = mid -1
else:
left = mid + 1
return answer
def dfs(cur, value):
lv, rv = 0, 0
global cnt
if cur.left != None:
lv = dfs(cur.left, value)
if cur.right != None:
rv = dfs(cur.right, value)
if cur.item + lv + rv <= value:
return cur.item + lv + rv
if cur.item + min(lv, rv) <= value:
cnt += 1
return cur.item + min(lv, rv)
if cur.item > value:
cnt += 10**7
return cur.item
cnt += 2
return cur.item
|