-
Notifications
You must be signed in to change notification settings - Fork 0
/
2265.py
34 lines (29 loc) · 1.01 KB
/
2265.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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
# Child Nodes pass up (sum including itself, num including itself, valid nodes n)
def dfs(node):
this_sum = node.val
this_n = 1
valid_nodes = 0
if node.left:
left = dfs(node.left)
this_sum += left[0]
this_n += left[1]
valid_nodes += left[2]
if node.right:
right = dfs(node.right)
this_sum += right[0]
this_n += right[1]
valid_nodes += right[2]
this_ans = int(this_sum / this_n)
if this_ans == node.val:
valid_nodes += 1
return (this_sum, this_n, valid_nodes)
ans = dfs(root)
return ans[2]