-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathaveragePropertyBinaryTree.py
130 lines (109 loc) · 2.44 KB
/
averagePropertyBinaryTree.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
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
119
120
121
122
123
124
125
126
127
128
129
130
# '''
# Binary Tree Property Check: Each Node is Average of All Descendents
#
# Given a binary tree check if each node is the average of all its descendants.
# ```
# >>>print_tree(root_1)
# 2 => (2 + 2 + 2+ 1 + 3) / 5 == 2
# / \
# 2 2 => (1 + 3) / 2 == 2
# / / \
# 2 1 3
#
# >>>check_avg_property(root_1)
# True
#
# >>>print_tree(root_2)
# 3 => (2 + 2 + 4 + 3 + 5) = 16, 16 / 5 != 3
# / \
# 2 4
# / / \
# 2 3 5
#
# >>>check_avg_property(root_2)
# False
# ```
#
# 3
# /
# 3
# /
# 3
# /
# 1
# '''
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 3
# check_avg(2)
# check_avg(2)
# check_avg(4)
def retrievesElements(root):
if not root:
return True
if not check_avg_property(root):
return False
if not retrievesElements(root.right):
return False
if not retrievesElements(root.left):
return False
return True
# if root.left:
# if not check_avg_property(root.left):
# return False
# if root.right:
# if not check_avg_property(root.right):
# return False
# return check_avg_property(root)
# 3 => (2 + 2 + 4 + 3 + 5) = 16, 16 / 5 != 3
# / \
# 2 4
# / / \
# 2 3 5
def check_avg_property(root):
if not root:
return 0, 0 #n_childs, sum_childs
l_nchilds,l_sum_childs = check_avg_property(root.left)
r_nchilds, r_sum_childs = check_avg_property(root.right)
if
return
def check_avg_property_not_optimized(root):
# dfs
q = [root.left, root.right]
n_childs = 0
sum_childs = 0
#
while q:
node = q.pop(0)
n_childs += 1
sum_childs += node.val
if node.left: q.append(node.left)
if node.right: q.append(node.right)
return root.val == sum_childs / n_childs
tree = Node(2,
Node(2,
Node(2)
),
Node(2,
Node(1),
Node(3)))
assert check_avg_property(tree)
tree = Node(3,
Node(2,
Node(2)
),
Node(4,
Node(3),
Node(5)))
assert False == check_avg_property(tree)
tree = Node(2,
Node(2,
Node(2)
),
Node(1,
Node(2),
Node(3)))
assert False == check_avg_property(tree)