# 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:
self.max_avg = 0
def dfs(node):
if not node:
return (0, 0) # sum, count
left_sum, left_count = dfs(node.left)
right_sum, right_count = dfs(node.right)
curr_sum = node.val + left_sum + right_sum
curr_count = 1 + left_count + right_count
curr_avg = curr_sum / curr_count
self.max_avg = max(self.max_avg, curr_avg)
return (curr_sum, curr_count)
dfs(root)
return self.max_avg
// Definition for a binary tree node.
// struct TreeNode {
// int val;
// TreeNode *left;
// TreeNode *right;
// TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
class Solution {
public:
double maxAvg = 0;
pair dfs(TreeNode* node) {
if (!node) return {0, 0};
auto left = dfs(node->left);
auto right = dfs(node->right);
int currSum = node->val + left.first + right.first;
int currCount = 1 + left.second + right.second;
double currAvg = (double)currSum / currCount;
maxAvg = max(maxAvg, currAvg);
return {currSum, currCount};
}
double maximumAverageSubtree(TreeNode* root) {
dfs(root);
return maxAvg;
}
};
// Definition for a binary tree node.
// public class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode(int x) { val = x; }
// }
class Solution {
private double maxAvg = 0;
public double maximumAverageSubtree(TreeNode root) {
dfs(root);
return maxAvg;
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0}; // sum, count
int[] left = dfs(node.left);
int[] right = dfs(node.right);
int currSum = node.val + left[0] + right[0];
int currCount = 1 + left[1] + right[1];
double currAvg = (double)currSum / currCount;
maxAvg = Math.max(maxAvg, currAvg);
return new int[]{currSum, currCount};
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
var maximumAverageSubtree = function(root) {
let maxAvg = 0;
function dfs(node) {
if (!node) return [0, 0]; // sum, count
let [leftSum, leftCount] = dfs(node.left);
let [rightSum, rightCount] = dfs(node.right);
let currSum = node.val + leftSum + rightSum;
let currCount = 1 + leftCount + rightCount;
let currAvg = currSum / currCount;
maxAvg = Math.max(maxAvg, currAvg);
return [currSum, currCount];
}
dfs(root);
return maxAvg;
};
Given the root of a binary tree, the goal is to find the maximum average value among all possible subtrees of the tree. A subtree is defined as any node and all its descendants. The average of a subtree is the sum of all node values in that subtree divided by the number of nodes in it.
root: The root node of the binary tree.
At first glance, the problem seems to require checking every possible subtree and calculating its average. A brute-force approach would be to, for each node, traverse its entire subtree and compute the sum and count of nodes, then evaluate the average. However, this would be inefficient, as the same nodes would be counted multiple times across overlapping subtrees.
To optimize, we can realize that a post-order traversal (processing children before the parent) allows us to compute the sum and count of nodes for each subtree efficiently, reusing results. For each node, if we know the sum and count of its left and right subtrees, we can quickly compute the sum and count for the subtree rooted at that node. This avoids redundant calculations and ensures we only traverse each node once.
The key insight is to use recursion to return both the sum and count for each subtree, and update the maximum average found so far at each step.
This approach ensures each node is visited exactly once, and all calculations for subtree sums and counts are done efficiently.
Sample Input:
5
/ \
6 1
The maximum average among all subtrees is 6.0 (from the subtree rooted at node 6).
As the traversal proceeds:
The Maximum Average Subtree problem is efficiently solved by leveraging post-order traversal to compute subtree sums and counts recursively. By updating the maximum average found at each node, we avoid redundant computations and ensure an optimal O(N) solution. This approach is both elegant and practical, demonstrating the power of recursion and careful traversal in tree-based problems.