Skip to content

1120. Maximum Average Subtree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct T {
  int sum;
  int count;
  double maxAverage;
};

class Solution {
 public:
  double maximumAverageSubtree(TreeNode* root) {
    return maximumAverage(root).maxAverage;
  }

 private:
  T maximumAverage(TreeNode* root) {
    if (root == nullptr)
      return {0, 0, 0.0};

    const T left = maximumAverage(root->left);
    const T right = maximumAverage(root->right);

    const int sum = root->val + left.sum + right.sum;
    const int count = 1 + left.count + right.count;
    const double maxAverage =
        max({sum / (double)count, left.maxAverage, right.maxAverage});
    return {sum, count, maxAverage};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public double maximumAverageSubtree(TreeNode root) {
    return maximumAverage(root).maxAverage;
  }

  private record T(int sum, int count, double maxAverage) {}

  private T maximumAverage(TreeNode root) {
    if (root == null)
      return new T(0, 0, 0.0);

    T left = maximumAverage(root.left);
    T right = maximumAverage(root.right);

    final int sum = root.val + left.sum + right.sum;
    final int count = 1 + left.count + right.count;
    final double maxAverage =
        Math.max(sum / (double) count, Math.max(left.maxAverage, right.maxAverage));
    return new T(sum, count, maxAverage);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from dataclasses import dataclass


@dataclass(frozen=True)
class T:
  summ: int
  count: int
  maxAverage: int


class Solution:
  def maximumAverageSubtree(self, root: TreeNode | None) -> float:
    def maximumAverage(root: TreeNode | None) -> T:
      if not root:
        return T(0, 0, 0)

      left = maximumAverage(root.left)
      right = maximumAverage(root.right)

      summ = root.val + left.summ + right.summ
      count = 1 + left.count + right.count
      maxAverage = max(summ / count, left.maxAverage, right.maxAverage)
      return T(summ, count, maxAverage)

    return maximumAverage(root).maxAverage