LeetCode - Binary Tree Level Order Traversal | Darren's Blog

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level
For space efficiency, we can use two variables to keep track of the number of remaining nodes in the current level, and the number of nodes in the next level.

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (root == null)

            return result;

 

        // Used as a queue to save children nodes explored in the next level

        Deque<TreeNode> nodesInALevel = new ArrayDeque<TreeNode>();

        nodesInALevel.add(root);

 

        // Values in the current level

        ArrayList<Integer> valuesInCurrentLevel = new ArrayList<Integer>();

 

        // remaining: number of remaining nodes in the current level;

        // newlyAdded: number of nodes for the next level

        int remaining = 1, newlyAdded = 0;

 

        while(remaining != 0) {

            TreeNode currentNode = nodesInALevel.poll();

            valuesInCurrentLevel.add(currentNode.val);

            remaining--;

            if (currentNode.left != null) {     // Save its left child (if any) to be explored in the next level

                nodesInALevel.add(currentNode.left);

                newlyAdded++;

            }

            if (currentNode.right != null) {    // Save its right child (if any) to be explored in the next level

                nodesInALevel.add(currentNode.right);

                newlyAdded++;

            }

            if (remaining == 0) {       // Current level is done; get ready for the next level

                remaining = newlyAdded;

                newlyAdded = 0;

                result.add(valuesInCurrentLevel);

                valuesInCurrentLevel = new ArrayList<Integer>();

            }

        }

        return result;

    }

Read full article from LeetCode - Binary Tree Level Order Traversal | Darren's Blog