103.binary-tree-zigzag-level-order-traversal.md

103. Binary Tree Zigzag Level Order Traversal

Clarification Questions

• No, it's clear from problem description.

Test Cases

Normal Cases

Input: 
Output: 

Edge / Corner Cases

Input: 
Output: 

fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
    val results = mutableListOf<List<Int>>()
    if (root == null) return results
    val queue = ArrayDeque<TreeNode>()
    queue.addLast(root)
    // Odd: left to right, even: right to left
    var level = 1
    while (queue.isNotEmpty()) {
        val size = queue.size
        val list = LinkedList<Int>()
        for (i in 0 until size) {
            val node = queue.removeFirst()
            if (level % 2 != 0) {
                list.add(node.`val`)
            } else {
                list.addFirst(node.`val`)
            }
            if (node.left != null) {
                queue.addLast(node.left)
            }
            if (node.right != null) {
                queue.addLast(node.right)
            }
        }
        results.add(list)
        level++
    }

    return results
}

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