Q4_4.java

import java.util.ArrayList;
import java.util.LinkedList;


public class Q4_4{
	public static void main(String[] args){
		int[] array ={1,2,3,4,5,6,7,8};
		TreeNode test = new Q4_3().arrayToBST(array, 0,7);
		ArrayList<LinkedList<TreeNode>>  result = new ArrayList<LinkedList<TreeNode>>();
		treeToLinkedLists2(test,result);
		for(LinkedList<TreeNode> list:result){
			for(TreeNode n : list){
				System.out.print(n.value);
			}
			System.out.println();
		}
		
	}
	static void treeToLinkedLists1(TreeNode root, ArrayList<LinkedList<TreeNode>>  lists, int layer){
		if(root == null)
			return;
		
		LinkedList<TreeNode> list;
		if(lists.size()==layer){
			list =  new LinkedList<TreeNode>();
			list.add(root);
			lists.add(list);
		}
		else 
			lists.get(layer).add(root);
		treeToLinkedLists1(root.left,lists,layer+1);
		treeToLinkedLists1(root.right,lists,layer+1);
			
	}
	static void treeToLinkedLists2(TreeNode root, ArrayList<LinkedList<TreeNode>> lists){
		if(root == null)
			return;
		LinkedList<TreeNode> list = new LinkedList<TreeNode>();
		list.add(root);
		lists.add(list);
		
		while(list.size()>0){
			LinkedList<TreeNode> nextList = new LinkedList<TreeNode>();
			for(TreeNode n : list){
				if(n.left != null)
					nextList.add(n.left);
				if(n.right!=null)
					nextList.add(n.right);
			}
			lists.add(nextList);
			list=nextList;
		}
			
	}
	
}