Задача: 637. Average of Levels in Binary Tree
Учитывая корень бинарного дерева, верните среднее значение узлов на каждом уровне в виде массива. Принимаются ответы в пределах 10-5 от фактического ответа.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: [3.00000,14.50000,11.00000]
👨💻 Алгоритм:
1⃣Обход дерева
Используйте обход в ширину (BFS) для обхода каждого уровня дерева.
2⃣Подсчет среднего значения
Для каждого уровня дерева подсчитайте сумму значений узлов и количество узлов, чтобы вычислить среднее значение.
3⃣Сохранение результата
Сохраните среднее значение каждого уровня в массив и верните его.
😎 Решение:
import java.util.LinkedList
import java.util.Queue
class Solution {
fun averageOfLevels(root: TreeNode?): List<Double> {
val result = mutableListOf<Double>()
val queue: Queue<TreeNode> = LinkedList()
queue.add(root)
while (queue.isNotEmpty()) {
var sum: Long = 0
val count = queue.size
for (i in 0 until count) {
val node = queue.poll()
sum += node.`val`
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
result.add(sum.toDouble() / count)
}
return result
}
}
👉Новости 👉Платформа