LeetCode Entry

103. Binary Tree Zigzag Level Order Traversal

19.02.2023 medium 2023 kotlin

for zigzag, we can skip a boolean variable and track result count.

103. Binary Tree Zigzag Level Order Traversal medium

blog post

    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> = mutableListOf<List<Int>>().also { res ->
            with(ArrayDeque<TreeNode>().apply { root?.let { add(it) } }) {
                while (isNotEmpty()) {
                    val curr = LinkedList<Int>().apply { res.add(this) }
                    repeat(size) {
                        with(poll()) {
                            with(curr) { if (res.size % 2 == 0) addFirst(`val`) else addLast(`val`) }
                            left?.let { add(it) }
                            right?.let { add(it) }
                        }
                    }
                }
            }
        }

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/123

Intuition

Each BFS step gives us a level, which one we can reverse if needed.

Approach

• for zigzag, we can skip a boolean variable and track result count.

  Complexity

• Time complexity: \(O(n)\)
• Space complexity: \(O(n)\)