LeetCode-in-All

102. Binary Tree Level Order Traversal

Medium

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

Constraints:

Solution

import com_github_leetcode.TreeNode
import scala.collection.mutable.{ListBuffer, Queue}

/*
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 *   var value: Int = _value
 *   var left: TreeNode = _left
 *   var right: TreeNode = _right
 * }
 */
object Solution {
    def levelOrder(root: TreeNode): List[List[Int]] = {
        val result = ListBuffer[List[Int]]()
        if (root == null) {
            return result.toList
        }
        val queue = Queue[TreeNode]()
        queue.enqueue(root)
        queue.enqueue(null)
        val level = ListBuffer[Int]()

        while (queue.nonEmpty) {
            val current = queue.dequeue()
            if (current != null) {
                level += current.value
                if (current.left != null) {
                    queue.enqueue(current.left)
                }
                if (current.right != null) {
                    queue.enqueue(current.right)
                }
            } else if (level.nonEmpty) {
                result += level.toList
                level.clear()
                queue.enqueue(null)
            }
        }

        result.toList
    }
}