LintCode 69 · Binary Tree Level Order Traversal.java

	/**
	* Definition of TreeNode:
	* public class TreeNode {
	* public int val;
	* public TreeNode left, right;
	* public TreeNode(int val) {
	* this.val = val;
	* this.left = this.right = null;
	* }
	* }
	*/
	// Approach #1 - BFS - T O(#OfNodes).
	public class Solution {
	/**
	* @param root: A Tree
	* @return: Level order a list of lists of integer
	*/
	public List<List<Integer>> levelOrder(TreeNode root) {
	// write your code here
	if (root == null) {
	return new LinkedList<>();
	}
	result = new LinkedList<>();
	bfs(root);
	return result;
	}
	private List<List<Integer>> result;
	private void bfs(TreeNode root) {
	Queue<TreeNode> queue = new ArrayDeque<>();
	queue.offer(root);
	while (!queue.isEmpty()) {
	int size = queue.size();
	result.add(new LinkedList<>());
	while (size-- > 0) {
	TreeNode node = queue.poll();
	result.get(result.size() - 1).add(node.val);
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	}
	}
	}

view raw LintCode 69 · Binary Tree Level Order Traversal.java hosted with ❤ by GitHub