Daily LeetCode Challenge - 103. Binary Tree Zigzag Level Order Traversal

Problem From.

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

오늘 문제는 한 depth 에서 왼쪽에서 오른쪽으로 노드를 탐색했다면 다음 depth 에서는 오른쪽에서 왼쪽으로 노드를 탐색하여 반환하는 문제였다.

얼마전에 푼 BFS 와 마찬가지로 한 depth 에 들어온 노드를 모두 탐색한 뒤 다음으로 넘어가는 식으로 풀었다.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        val queue : Queue<TreeNode> = LinkedList()
        val result = mutableListOf<LinkedList<Int>>()
        if (root == null) return result
        var leftToRight = true // if true, add elements in normally else add in reverse
        queue.add(root)
        while (queue.isNotEmpty()) {
            val depth = LinkedList<Int>()
            var size = queue.size
            while (size > 0) {
                var current = queue.poll()
                if (leftToRight.not()) depth.addFirst(current.`val`)
                else depth.add(current.`val`)
                current.left?.let { queue.offer(it) }
                current.right?.let { queue.offer(it) }
                --size
            }
            result.add(depth)
            leftToRight = !leftToRight
        }
        return result
    }
}