1080. Insufficient Nodes in Root to Leaf Paths
Idea
root에서 leaf 노드 까지 도달했을때 limit - cumulative sum 값을 구하고,
postorder 방식으로 search 하면서 internal node들에 들해서 update한다.
(cur를 기준으로 cur.left와 cur.right둘다 없다면, 그 노드는 None으로 만들어 삭제)
In [39]:
1
2
3
from typing import List
from binarytree import build, Node, tree
import random
In [96]:
1
2
3
4
5
6
7
8
9
10
class Solution:
def sufficientSubset(self, cur, limit):
if cur.left == cur.right:
return None if limit > cur.value else cur
if cur.left:
cur.left = self.sufficientSubset(cur.left, limit - cur.value)
if cur.right:
cur.right = self.sufficientSubset(cur.right, limit - cur.value)
return cur if cur.left or cur.right else None
sol = Solution()
In [97]:
1
2
null = None
A, limit = [1,2,-3,-5,null,4,null], -1
In [98]:
1
2
3
4
root = build(A)
root.pprint()
root = sol.sufficientSubset(root, limit)
root.pprint()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1__
/ \
_2 -3
/ /
-5 4
1__
\
-3
/
4
In [107]:
1
2
3
4
5
6
root = tree(height=4)
root.pprint()
limit = 90
print("limit:", limit)
ans = sol.sufficientSubset(root, limit)
ans.pprint() if ans else None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
___________18______________
/ \
_______16_____ _______26___
/ \ / \
_2___ ___20 _30___ _9__
/ \ / \ / \ / \
27 _1 29 4 14 _12 21 19
/ \ \ / / /
25 8 5 3 13 6
limit: 90
18______________
\
_______26
/
_30___
/ \
14 _12
/ /
3 13
In [108]:
1
18 + 26 + 30 + 14 + 3
1
91
Leave a comment