-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbintreecamera.py
More file actions
90 lines (74 loc) · 2.45 KB
/
Copy pathbintreecamera.py
File metadata and controls
90 lines (74 loc) · 2.45 KB
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
#Definition for a binary tree node.
from typing import List
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __repr__(self):
return f"Node({self.val}, {self.left}, {self.right})"
@staticmethod
def createTree(l: List) -> 'TreeNode':
# No empty trees since number notes >= 1
r = TreeNode(l.pop(0))
s = [(r, 'left'), (r, 'right')]
while len(l) > 0:
print(f"{l} : {s}")
v = l.pop(0)
a = s.pop(0)
if v is not None:
if a[1] == 'left':
nn = a[0].left = TreeNode(v)
elif a[1] == 'right':
nn = a[0].right = TreeNode(v)
else:
raise Exception("stack error")
s.extend([(nn, 'left'), (nn, 'right')])
return r
class Solution:
def __init__(self, debug=False):
self.debug = debug
def minCameraCover(self, root: TreeNode) -> int:
rv = self.minCameraCover_h(root)
return rv[0] if rv[1] > 0 else rv[0] + 1
def minCameraCover_h(self, root) -> (int, int):
"Returns count needed for tree below root, and if below root is already monitored"
if root is None:
return (0, 1)
rv1 = self.minCameraCover_h(root.left)
rv2 = self.minCameraCover_h(root.right)
if rv1[1] > 0 and rv2[1] > 0:
return (rv1[0] + rv2[0], max(rv1[1], rv2[1]) - 1)
else:
return (rv1[0] + rv2[0] + 1, 2)
def test1():
in1 = [0, 0, None, 0, 0]
t1 = TreeNode.createTree(in1)
print(repr(t1))
assert Solution(True).minCameraCover(t1) == 1
def test2():
in2 = [0, 0, None, 0, None, 0, None, None, 0]
t2 = TreeNode.createTree(in2)
print(repr(t2))
assert Solution(True).minCameraCover(t2) == 2
def test3():
# selfmade test
in3 = [0, 0, 0, 0, 0, 0, 0]
t3 = TreeNode.createTree(in3)
print(repr(t3))
assert Solution(True).minCameraCover(t3) == 2
def test4():
in4 = [0]
t4 = TreeNode.createTree(in4)
print(repr(t4))
assert Solution(True).minCameraCover(t4) == 1
def test5():
in5 = [0,0,None,None,0,0,None,None,0,0]
t5 = TreeNode.createTree(in5)
print(repr(t5))
assert Solution(True).minCameraCover(t5) == 2
def test6():
in6 = [0,None,0,None,0,None,0]
t6 = TreeNode.createTree(in6)
print(repr(t6))
assert Solution(True).minCameraCover(t6) == 2