Задача: 1120. Maximum Average Subtree
Сложность: medium

Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.

Поддерево дерева — это любой узел этого дерева плюс все его потомки.

Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

class Solution {
    class State {
        var nodeCount: Int
        var valueSum: Int
        var maxAverage: Double
        
        init(_ nodes: Int, _ sum: Int, _ maxAvg: Double) {
            self.nodeCount = nodes
            self.valueSum = sum
            self.maxAverage = maxAvg
        }
    }
    
    func maximumAverageSubtree(_ root: TreeNode?) -> Double {
        return maxAverage(root).maxAverage
    }
    
    private func maxAverage(_ root: TreeNode?) -> State {
        guard let node = root else {
            return State(0, 0, 0)
        }
        
        let left = maxAverage(node.left)
        let right = maxAverage(node.right)
        
        let nodeCount = left.nodeCount + right.nodeCount + 1
        let sum = left.valueSum + right.valueSum + node.val
        let currentAverage = Double(sum) / Double(nodeCount)
        let maxAverage = max(currentAverage, max(left.maxAverage, right.maxAverage))
        
        return State(nodeCount, sum, maxAverage)
    }
}

Ставь 👍 и забирай 📚 Базу знаний