Задача: 637. Average of Levels in Binary Tree
Сложность: easy

Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]

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

1⃣Обход дерева: Используйте обход в ширину (BFS) для обхода каждого уровня дерева.

2⃣Подсчет среднего значения: Для каждого уровня дерева подсчитайте сумму значений узлов и количество узлов, чтобы вычислить среднее значение.

3⃣Сохранение результата: Сохраните среднее значение каждого уровня в массив и верните его.

😎 Решение:

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    func averageOfLevels(_ root: TreeNode?) -> [Double] {
        guard let root = root else { return [] }
        
        var result = [Double]()
        var queue: [TreeNode] = [root]
        
        while !queue.isEmpty {
            var levelSum = 0
            let levelCount = queue.count
            for _ in 0..<levelCount {
                let node = queue.removeFirst()
                levelSum += node.val
                if let left = node.left { queue.append(left) }
                if let right = node.right { queue.append(right) }
            }
            result.append(Double(levelSum) / Double(levelCount))
        }
        
        return result
    }
}

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