Maximum Average Subtree
Description
Given the root of a binary tree, return the maximum average value of any subtree (sum of values / number of nodes).
Examples
root = [5,6,1]6.0The subtree rooted at node 6 contains only itself, so its average is 6/1 = 6.0. For each subtree, the average is calculated as (sum of all node values in subtree) / (count of nodes in subtree), and the maximum across all subtrees is returned.
root = [1]1.0Edge case with a single-element array.
root = [4,2,6,1,3,5,7]7.0This binary tree has multiple subtrees with different averages. Leaf nodes have the highest averages: node 1 (avg=1.0), node 3 (avg=3.0), node 5 (avg=5.0), and node 7 (avg=7.0). The subtree rooted at node 2 has average (2+1+3)/3=2.0, and the subtree rooted at node 6 has average (6+5+7)/3=6.0. The maximum average is 7.0 from the leaf node 7.
Constraints
- •
1 ≤ nodes ≤ 5000
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.