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:

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Solution

import 'dart:collection';

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   int val;
 *   TreeNode? left;
 *   TreeNode? right;
 *   TreeNode([this.val = 0, this.left, this.right]);
 * }
 */
class Solution {
  List<List<int>> levelOrder(TreeNode? root) {
    List<List<int>> result = [];
    if (root == null) {
      return result;
    }

    Queue<TreeNode?> queue = Queue<TreeNode?>();
    queue.add(root);
    queue.add(null); // Marker for level end

    List<int> level = [];

    while (queue.isNotEmpty) {
      root = queue.removeFirst();
      while (queue.isNotEmpty && root != null) {
        level.add(root.val);
        if (root.left != null) {
          queue.add(root.left);
        }
        if (root.right != null) {
          queue.add(root.right);
        }
        root = queue.removeFirst();
      }

      result.add(level);
      level = []; // Reset for the next level

      if (queue.isNotEmpty) {
        queue.add(null); // Marker for the next level end
      }
    }

    return result;
  }
}

This site is open source. Improve this page.