LeetCode 107. Обход порядка уровней двоичного дерева II

Примечания LeetCode [56]: решение BFS Kotlin

Проблема

Интуиция

Примените BFS для выполнения обхода порядка уровней от корня и обратного порядка.

Код

class Solution {
    fun levelOrderBottom(root: TreeNode?): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        root?.let {
            val queue: Queue<TreeNode> = LinkedList()
            queue.offer(it)
            while (queue.isNotEmpty()) {
                val level = mutableListOf<Int>()
                for (i in queue.indices) {
                    val node = queue.poll()
                    level.add(node.`val`)
                    node.left?.let { queue.offer(it) }
                    node.right?.let { queue.offer(it) }
                }
                result.add(0, level)
            }
        }
        return result
    }
}

Анализ сложности

• Временная сложность: O(n)
• Сложность пространства: O(n)