102.Binary Tree Level Order Traversal


LeetCode 102. Binary Tree Level Order Traversal

  • 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: []

Method 1

【O(n)time∣O(n)space】
package Leetcode.Trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhengstars
 * @date 2024/04/08
 */
public class BinaryTreeLevelOrderTraversal {
    public static List<List<Integer>> levelOrder(TreeNode root) {
        // Initialize our result list
        List<List<Integer>> res = new ArrayList<>();

        // null-check: if the binary tree is empty, directly return the empty result list.
        if(root == null){
            return res;
        }

        // Initialize our queue with the root node
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        // While our queue is not empty
        while (!queue.isEmpty()){
            // Initialize a new list to store the current level
            List<Integer> level = new ArrayList<>();

            // Get the number of nodes at the current level
            int size = queue.size();

            // Loop over all the nodes at the current level
            for(int i = 0; i < size; i++){
                // Dequeue a node from the front of the queue
                TreeNode node = queue.remove();

                // Add the node's value to the current level's list
                level.add(node.val);

                // Enqueue the current node's left and right children to the queue
                if(node.left != null){
                    queue.add(node.left);
                }

                if(node.right != null){
                    queue.add(node.right);
                }
            }

            // After we've processed all the nodes at the current level, 
            // add the current level's list to our result list.
            res.add(level);
        }

        // Finally, return the result list.
        return res;
    }


    public static void main(String[] args) {

        // Test case 1: a complete binary tree
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        // Expected output: [[3],[9,20],[6,2,15,7]].
        System.out.println(levelOrder(root));

        // Test case 2: a binary tree with only one node.
        root = new TreeNode(1);
        // Expected output: [[1]].
        System.out.println(levelOrder(root));

        // Test case 3: an empty binary tree (null root).
        root = null;
        // Expected output: [].
        System.out.println(levelOrder(root));
    }
} 



Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 3223. Minimum Length of String After Operations
  • 1208. Get Equal Substrings Within Budget
  • 2730. Find the Longest Semi-Repetitive Substring
  • 1493. Longest Subarray of 1's After Deleting One Element
  • 2275. Largest Combination With Bitwise AND Greater Than Zero