Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1120 with 12 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1120 # by problem number
lcpy gen -s maximum_average_subtree # by problem name
root of a binary tree, return the maximum average value of a subtree of that tree. Answers within 10^-5 of the actual answer will be accepted.
A subtree of a tree is any node of that tree plus all its descendants.
The average value of a tree is the sum of its values, divided by the number of nodes.
Input: root = [5,6,1]
Output: 6.00000
Explanation: For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4. For the node with value = 6 we have an average of 6 / 1 = 6. So the answer is 6 which is the maximum.
Input: root = [0,null,1]
Output: 1.00000
from leetcode_py import TreeNode
class Solution:
# Time: O(n)
# Space: O(h) for the recursion stack
def maximum_average_subtree(self, root: TreeNode[int] | None) -> float:
ans = 0.0
def dfs(node: TreeNode[int] | None) -> tuple[int, int]:
nonlocal ans
if node is None:
return 0, 0
left_sum, left_n = dfs(node.left)
right_sum, right_n = dfs(node.right)
total = node.val + left_sum + right_sum
count = 1 + left_n + right_n
ans = max(ans, total / count)
return total, count
dfs(root)
return ans
| Time | Space |
|---|---|
| O(n) | O(h) for the recursion stack |