Leetcode 1091 Solution

This article provides solution to leetcode question 1091 (maximum-average-subtree)

https://leetcode.com/problems/maximum-average-subtree

Solution

# 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 maximumAverageSubtree(self, root: Optional[TreeNode]) -> float: ans = 0
def dfs(node): nonlocal ans
if not node: return 0, 0
left_sum, left_cnt = dfs(node.left) right_sum, right_cnt = dfs(node.right)
node_sum = node.val + left_sum + right_sum node_cnt = 1 + left_cnt + right_cnt
ans = max(ans, node_sum / node_cnt)
return node_sum, node_cnt
dfs(root)
return ans