1120. Maximum Average Subtree

public class Solution {
    class State {
        public int nodeCount;
        public int valueSum;
        public double maxAverage;
        public State(int nodes, int sum, double maxAvg) {
            this.nodeCount = nodes;
            this.valueSum = sum;
            this.maxAverage = maxAvg;
        }
    }
    public double MaximumAverageSubtree(TreeNode root) {
        return maxAverage(root).maxAverage;
    }
    private State maxAverage(TreeNode root) {
        if (root == null) {
            return new State(0, 0, 0);
        }
        State left = maxAverage(root.left);
        State right = maxAverage(root.right);
        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root.val;
        double currentAverage = (1.0 * sum) / nodeCount;
        double maxAverage = Math.Max(currentAverage, Math.Max(left.maxAverage, right.maxAverage));
        return new State(nodeCount, sum, maxAverage);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    class State {
        public int nodeCount;
        public int valueSum;
        public double maxAverage;
        public State(int nodes, int sum, double maxAvg) {
            this.nodeCount = nodes;
            this.valueSum = sum;
            this.maxAverage = maxAvg;
        }
    }
    public double MaximumAverageSubtree(TreeNode root) {
        return maxAverage(root).maxAverage;
    }
    private State maxAverage(TreeNode root) {
        if (root == null) {
            return new State(0, 0, 0);
        }
        State left = maxAverage(root.left);
        State right = maxAverage(root.right);
        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root.val;
        double currentAverage = (1.0 * sum) / nodeCount;
        double maxAverage = max(currentAverage, max(left.maxAverage, right.maxAverage));
        return new State(nodeCount, sum, maxAverage);
    }
}

class Solution {
    class State {
        int nodeCount;

        int valueSum;

        double maxAverage;

        State(int nodes, int sum, double maxAverage) {
            this.nodeCount = nodes;
            this.valueSum = sum;
            this.maxAverage = maxAverage;
        }
    }

    public double maximumAverageSubtree(TreeNode root) {
        return maxAverage(root).maxAverage;
    }

    State maxAverage(TreeNode root) {
        if (root == null) {
            return new State(0, 0, 0);
        }

        State left = maxAverage(root.left);
        State right = maxAverage(root.right);

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root.val;
        double maxAverage = Math.max(
                (1.0 * (sum)) / nodeCount,
                Math.max(right.maxAverage, left.maxAverage)
        );

        return new State(nodeCount, sum, maxAverage);
    }
}

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    maximumAverageSubtree(root) {
        return this.maxAverage(root).maxAverage;
    }

    maxAverage(node) {
        if (!node) {
            return { nodeCount: 0, valueSum: 0, maxAverage: 0 };
        }

        const left = this.maxAverage(node.left);
        const right = this.maxAverage(node.right);

        const nodeCount = left.nodeCount + right.nodeCount + 1;
        const valueSum = left.valueSum + right.valueSum + node.val;
        const currentAverage = valueSum / nodeCount;
        const maxAverage = Math.max(currentAverage, left.maxAverage, right.maxAverage);

        return { nodeCount, valueSum, maxAverage };
    }
}

package main

import "math"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type State struct {
    nodeCount int
    valueSum  int
    maxAverage float64
}

func maximumAverageSubtree(root *TreeNode) float64 {
    return maxAverage(root).maxAverage
}

func maxAverage(node *TreeNode) State {
    if node == nil {
        return State{0, 0, 0}
    }

    left := maxAverage(node.Left)
    right := maxAverage(node.Right)

    nodeCount := left.nodeCount + right.nodeCount + 1
    valueSum := left.valueSum + right.valueSum + node.Val
    currentAverage := float64(valueSum) / float64(nodeCount)
    maxAverage := math.Max(currentAverage, math.Max(left.maxAverage, right.maxAverage))

    return State{nodeCount, valueSum, maxAverage}
}

Algorithm

Инициализация и 정의 State:

Определите класс State для хранения количества узлов в поддереве, суммы значений узлов в поддереве и максимального среднего значения поддерева.

Постобход (postorder traversal):

Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.

Вычисление максимального среднего значения:

Используйте значения, полученные от дочерних узлов, для вычисления среднего значения для текущего узла и обновите maxAverage, если новое среднее значение больше текущего максимума.

😎