LintCode 242 · Convert Binary Tree to Linked Lists by Depth.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;
	* }
	* }
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	// Approach #1 - T O(#OfNodes) - do a BFS w/ levels. Then just simulate and fill the LinkedList.
	public class Solution {
	/**
	* @param root the root of binary tree
	* @return a lists of linked list
	*/
	public List<ListNode> binaryTreeToLists(TreeNode root) {
	// handle corner cases
	if (root == null) {
	return new LinkedList<>();
	}
	result = new LinkedList<>();
	bfs(root);
	return result;
	}
	private List<ListNode> result;
	private void bfs(TreeNode root) {
	Queue<TreeNode> queue = new ArrayDeque<>();
	queue.offer(root);
	while (!queue.isEmpty()) {
	int size = queue.size();
	ListNode dummyPreHead = new ListNode(-1);
	ListNode current = dummyPreHead;
	while (size-- > 0) {
	TreeNode node = queue.poll();
	current.next = new ListNode(node.val);
	current = current.next;
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	result.add(dummyPreHead.next);
	}
	}
	}

view raw LintCode 242 · Convert Binary Tree to Linked Lists by Depth.java hosted with ❤ by GitHub