Maximum Average Subtree Demand
Uber's operations team continuously optimizes driver distribution and pricing strategies based on real-time demand. To identify key zones for intervention, they've modeled geographical areas as a hierarchical tree structure. Each node in this tree represents a specific zone and carries a numerical demand score. The goal is to pinpoint the most impactful areas by finding the subtree that exhibits the highest average demand score.
Implement a function maxAverageSubtreeDemand that, given the root of a binary tree, identifies and returns the demand score (val) of the root node of the subtree with the highest average demand. The average demand of a subtree is calculated as the sum of demand values of all nodes within that subtree divided by the total number of nodes in that subtree.
Input:
root: The root node of a binary tree. Each TreeNode has an integer val (representing demand), and left and right pointers to child TreeNodes or null.Output:
number: The val of the root node of the subtree that has the maximum average demand. If the tree is empty, return 0. If multiple subtrees have the same maximum average demand, any corresponding node's val is acceptable.root is null, return 0.val) can be positive, negative, or zero.val.Examples
Example 1
Input:
root = [5,2,-3]
Output:
2
Note:
Subtree with root 2: sum=2, count=1, avg=2. Subtree with root -3: sum=-3, count=1, avg=-3. Subtree with root 5 (full tree): sum=5+2-3=4, count=3, avg=4/3≈1.33. The maximum average is 2, from the subtree rooted at node 2.
Example 2
Input:
root = [-1,-2,-3,-4,-5]
Output:
-3
Note:
Subtree with root -4: avg=-4. Subtree with root -5: avg=-5. Subtree with root -2 (nodes -2,-4,-5): sum=-11, count=3, avg≈-3.67. Subtree with root -3: avg=-3. Subtree with root -1 (full tree): sum=-15, count=5, avg=-3. The maximum average is -3, which occurs at node -1 and node -3. Returning -3 is acceptable.
Example 3
Input:
root = [10]
Output:
10
Note:
The only subtree is the root itself. Sum=10, count=1, average=10.
Example 4
Input:
root = []
Output:
0
Note:
An empty tree, as per clarifications, should return 0.
Constraints
[0, 10^4].-10^5 <= Node.val <= 10^5.O(N) in worst case, O(log N) for balanced trees).val is required.Loading editor...