Leetcode 1091 Solution
This article provides solution to leetcode question 1091 (maximum-average-subtree).
Access this page by simply typing in "lcs 1091" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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