Question

Formatted question description: https://leetcode.ca/all/102.html

102	Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

@tag-tree

Algorithm

The typical breadth-first search BFS application, but here is a little more complicated, to separate the numbers of each layer and store them in a two-dimensional vector.

The general idea is basically the same, create a queue, and then put the root node first Go in, then find the left and right child nodes of the root node, then remove the root node.

At this time, the elements in the queue are all the nodes in the next layer. Use a for loop to traverse them, and then store them in a one-dimensional vector to traverse After that, save the one-dimensional vector into the two-dimensional vector

Note

Use the null insertion method to mark each layer, is one way of marking level ending.

Pay attention to below:

1. The boundary problem of null, eg has only one root=1. Whenever it encounters null, first check whether q is empty. If q is empty, it will be the last, break directly If q is not empty, then offer a null as the end sign of the next layer

2. Note that the implementation of queue uses linkedlist, but arraylist does not work (removeFirst, removeLast are not supported)

Code

Java

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

public class Binary_Tree_Level_Order_Traversal {

	public static void main(String[] args) {

	}

	/**
	Definition for a binary tree node.
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	}
	 */

    class Solution_countAsMarker {
        public List<List<Integer>> levelOrder(TreeNode root) {

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

            if (root == null) {
                return result;
            }

            // @note: use level count as marker of each level, instead of adding an extra null as marker
            int currentLevelCount = 0;
            int nextLevelCount = 0;

            // initialization
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(root);
            currentLevelCount++;

            List<Integer> currentLevelList = new ArrayList<>();
            while (!q.isEmpty()) {
                TreeNode currentNode = q.poll();
                currentLevelCount--;

                currentLevelList.add(currentNode.val);

                // enqueue
                if (currentNode.left != null) {
                    q.offer(currentNode.left);
                    nextLevelCount++;
                }
                if (currentNode.right != null) {
                    q.offer(currentNode.right);
                    nextLevelCount++;
                }

                // check if end of current level
                if (currentLevelCount == 0) {
                    currentLevelCount = nextLevelCount;
                    nextLevelCount = 0;

                    // add this level int list to result
                    result.add(new ArrayList<>(currentLevelList));
                    currentLevelList.clear();
                }
            }

            return result;
        }
    }


    public class Solution {
	    public List<List<Integer>> levelOrder(TreeNode root) {

	    	List<List<Integer>> list = new ArrayList<List<Integer>>();

	    	if (root == null) {
	    		return list;
	    	}

	    	Queue<TreeNode> sk = new LinkedList<>();

	    	sk.offer(root);
	    	sk.offer(null);// @note: use null as marker for end of level

	    	List<Integer> oneLevel = new ArrayList<>();
	    	while (!sk.isEmpty()) {

	    		TreeNode current = sk.poll();

	    		if (current == null) {
	    			List<Integer> copy = new ArrayList<>(oneLevel);
	    			list.add(copy);

	    			// clean after one level recorded
	    			oneLevel.clear();// @memorize: this api

	    			// @note:@memorize: if stack is now empty then DO NOT add null, or else infinite looping
	    			// sk.offer(null); // add marker
	    			if (!sk.isEmpty()) {
	    				sk.offer(null); // add marker
	    			}

	    			continue;
	    		}

	    		oneLevel.add(current.val);

	    		// @note:@memorize: since using null as marker, then must avoid adding null when children are null
	    		// sk.offer(current.left);
	    		// sk.offer(current.right);
	    		if (current.left != null) {
	    			sk.offer(current.left);
	    		}
	    		if (current.right != null) {
	    			sk.offer(current.right);
	    		}

	    	}

	    	return list;
	    }
	}

}

All Problems

All Solutions