LeetCode 107. Binary Tree Level Order Traversal II

LeetCode Notes [56]: BFS Kotlin Solution

毛無山から見た富士山

Problem

Binary Tree Level Order Traversal II - LeetCode

Intuition

Apply BFS to perform level order traversal from the root, and reverse the order.

Code

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
    }
}

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)