CC150 4.4

4_4.java

/*
4.4 
Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth 
(e.g., if you have a tree with depth D, you'll have D linked lists).
*/

package cc150Test;

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

// 时间复杂度:  O(n)
// 空间复杂度:  O(n)

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}
public class Test {

	public static ArrayList<LinkedList<TreeNode>> createLinkedList(TreeNode root){
		ArrayList<LinkedList<TreeNode>> tree = new ArrayList<LinkedList<TreeNode>>();

		if( root == null ){
			return tree;
		}
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while( queue.size() != 0 ){
			int size = queue.size();
			LinkedList<TreeNode> head = new LinkedList<TreeNode>();
			for(int i = 0; i < size; i++){
				TreeNode temp = queue.poll();
				head.add(temp);
				if( temp.left != null ){
					queue.offer(temp.left);
				}
				if( temp.right != null ){
					queue.offer(temp.right);
				}
			}
			tree.add(head);
		}
		return tree;
	}

	public static void main(String[] args) {
		
		System.out.println("Tree #0");
		TreeNode root0 = null;   // 空树
		ArrayList<LinkedList<TreeNode>> tree0 = createLinkedList(root0);
		System.out.println( tree0.size() == 0 );

		System.out.println("");
		System.out.println("Tree #1");
		/*
					0
		*/
		TreeNode root1 = new TreeNode(0); //只有根节点0
		ArrayList<LinkedList<TreeNode>> tree1 = createLinkedList(root1);
		System.out.println( tree1.size() == 1 );		
		for(int i = 0; i < tree1.size(); i++){
			LinkedList<TreeNode> list = tree1.get(i);
			for(TreeNode temp:list){
				System.out.print(temp.val + "->");
			}
			System.out.println("");
		}
		System.out.println("");
		System.out.println("Tree #2");

		/*
		 *                 0
		 *                / \
		 *               1   2
		 *              /     \
		 *             3       4
		 */
		TreeNode root2 = new TreeNode(0);  
		TreeNode node21 = new TreeNode(1);TreeNode node22 = new TreeNode(2);
		TreeNode node23 = new TreeNode(3);TreeNode node24 = new TreeNode(4);
		root2.left = node21; root2.right = node22;
		node21.left = node23; node22.right = node24;

		ArrayList<LinkedList<TreeNode>> tree2 = createLinkedList(root2);
		System.out.println( tree2.size() == 3 );		
		for(int i = 0; i < tree2.size(); i++){
			LinkedList<TreeNode> list = tree2.get(i);
			for(TreeNode temp:list){
				System.out.print(temp.val + "->");
			}
			System.out.println("");
		}
		System.out.println("");
		System.out.println("Tree #3");
		/*
		 *                 0
		 *                / \
		 *               1   2
		 *                    \
		 *                     3
		 *                      \
		 *                       4
		 */
		TreeNode root3 = new TreeNode(0);
		TreeNode node31 = new TreeNode(1);TreeNode node32 = new TreeNode(2);
		TreeNode node33 = new TreeNode(3);TreeNode node34 = new TreeNode(4);
		root3.left = node31; root3.right = node32;
		node32.right = node33; node33.right = node34;		
		
		ArrayList<LinkedList<TreeNode>> tree3 = createLinkedList(root3);
		System.out.println( tree3.size() == 3 );		
		for(int i = 0; i < tree3.size(); i++){
			LinkedList<TreeNode> list = tree3.get(i);
			for(TreeNode temp:list){
				System.out.print(temp.val + "->");
			}
			System.out.println("");
		}
		System.out.println("");
	}		
}

great job