LC 102. Binary Tree Level Order Traversal - LeetCode

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,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	/**
	* @param root
	* @return
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
	// filter abnormal cases
	if (root == null) {
	return new LinkedList<>();
	}
	// core logic
	Queue<Entry> queue1 = new LinkedList<>();
	Queue<Entry> queue2 = new LinkedList<>();
	queue1.add(new Entry(root, 1));
	List<List<Integer>> resultList = new LinkedList<>();
	while (true) {
	if (queue1.isEmpty()) {
	return resultList;
	}
	List<Integer> row = new LinkedList<>();
	rowProcessing(queue1, queue2, row);
	resultList.add(row);
	Queue<Entry> tmp = queue1;
	queue1 = queue2;
	queue2 = tmp;
	}
	}
	private void rowProcessing(Queue<Entry> queue1, Queue<Entry> queue2, List<Integer> row) {
	while (!queue1.isEmpty()) {
	Entry currentEntry = queue1.remove();
	row.add(currentEntry.node.val);
	if (currentEntry.node.left != null) {
	queue2.add(new Entry(currentEntry.node.left, currentEntry.depth + 1));
	}
	if (currentEntry.node.right != null) {
	queue2.add(new Entry(currentEntry.node.right, currentEntry.depth + 1));
	}
	}
	}
	class Entry {
	TreeNode node;
	int depth;
	public Entry(TreeNode node, int depth) {
	this.node = node;
	this.depth = depth;
	}
	@Override
	public String toString() {
	return "Entry{" +
	"node=" + node +
	", depth=" + depth +
	'}';
	}
	}
	}

view raw LC 102. Binary Tree Level Order Traversal - Weekly Contest 67 - LeetCode.java hosted with ❤ by GitHub