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).

CC150-4.4-1.java

package POJ;

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

public class Main{
 
	/**
	 * 
	 *  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).
	 *  
	 *  @Runtime & spaces
	 * 	runtime: O(n)
	 * 	space: O(n)
	 * 
	 */
	public static void main(String[] args) {
		Main so=new Main();
	/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
		TreeNode root = new TreeNode(7);
        	root.left = new TreeNode(10);
        	root.right = new TreeNode(2);
        	root.left.left = new TreeNode(4);
        	root.left.right = new TreeNode(3);
        	root.left.right.right = new TreeNode(1);
        	root.right.left = new TreeNode(8);
        	root.right.left.left = new TreeNode(11);
		ArrayList<List<TreeNode>> traversal = so.createLevelLinkedList(root);
        	for (List<TreeNode> level : traversal) {
            		for (TreeNode node : level) {
                		System.out.print(node.val + "\t");
            		}
        		 System.out.println();
		 }
	}

	public ArrayList<List<TreeNode>> createLevelLinkedList(TreeNode root) {
		ArrayList<List<TreeNode>> result = new ArrayList<List<TreeNode>>();
		createLinkedList(root, result, 0);
		return result;
	}

	private void createLinkedList(TreeNode root,ArrayList<List<TreeNode>> result, int level) {
		// TODO Auto-generated method stub
		if(root==null)
			return;
		List<TreeNode> list=null;
		if(result.size()==level){
			//level not contained in result
			list=new LinkedList<TreeNode>();
			/* levels are always traversed in order. So, if this is the first
			 * time we've visited level i, we must have seen levels 0 through
			 * i-1. We can therefore safely add the level at the end.
			 * */
			result.add(list);
		}else{
			list=result.get(level);
		}
		list.add(root);
		createLinkedList(root.left, result, level+1);
		createLinkedList(root.right, result, level+1);
	}
}

CC150-4.4-2.java

package POJ;

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

public class Main{
 
	/**
	 * 
	 *  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).
	 *  
	 *  @Runtime & spaces
	 * 	runtime: O(n)
	 * 	space: O(n)
	 * 
	 */
	public static void main(String[] args) {
		Main so=new Main();
		/*	_______7______
	       /              \
	    __10__          ___2
	   /      \        /
	   4       3      _8
	            \    /
	             1  11 		*/
		TreeNode root = new TreeNode(7);
        root.left = new TreeNode(10);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(3);
        root.left.right.right = new TreeNode(1);
        root.right.left = new TreeNode(8);
        root.right.left.left = new TreeNode(11);
		ArrayList<List<TreeNode>> traversal = so.createLevelLinkedList(root);
        for (List<TreeNode> level : traversal) {
            for (TreeNode node : level) {
                System.out.print(node.val + "\t");
            }
            System.out.println();
        }
	}

	public ArrayList<List<TreeNode>> createLevelLinkedList(TreeNode root) {
		ArrayList<List<TreeNode>> result = new ArrayList<List<TreeNode>>();
		if(root==null)
			return result;
		List<TreeNode> current=new LinkedList<TreeNode>();
		current.add(root);
		while(current.size()>0){
			result.add(current);//add previous level
			List<TreeNode> parents=current;//go to next level
			current=new LinkedList<TreeNode>();
			for(TreeNode node: parents){
				if(node.left!=null)
					current.add(node.left);
				if(node.right!=null)
					current.add(node.right);
			}
			
		}
		return result;
	}
}