CC150: Tree to LinkedList

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

第一眼感觉就是level by level，用BFS就行了。

但是实际可以用类似一直pre-order的顺序遍历，但是我们需要一个额外的变量level，来记录当前点是对应第几层的。
No BFS version

public class Solution {
    public ArrayList<LinkedList<TreeNode>> create(TreeNode root) {
     ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
     createHelp(root, lists, 0);
     return lists;
    }

    private void createHelp(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) {
     if (root == null) {
      return;
     }

     if (lists.size() == level) {
      //for current level, we didn't create a new list
      LinkedList<TreeNode> list = new LinkedList<TreeNode>();
      list.add(root);
      lists.add(list);
     } else {
      LinkedList<TreeNode> list = lists.get(level);
      list.add(root);
     }

     createHelp(root.left, lists, level + 1);
     createHelp(root.right, lists, level + 1);
    }

    public ArrayList<LinkedList<TreeNode>> create(TreeNode root) {
     ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
     if (root == null) {
      return lists;
     }
 
     Queue<TreeNode> queue = new LinkedList<TreeNode>();
     queue.offer(root);
     while(!queue.isEmpty()) {
      int size = queue.size();
      LinkedList<TreeNode> list = new LinkedList<TreeNode>();
      for (int i = 0; i < size; i++) {
       TreeNode cur = queue.poll();
       if (cur.left != null) {
        queue.offer(cur.left);
       }
       if (cur.right != null) {
        queue.offer(cur.right);
       }
       list.add(cur);
      }
      lists.add(list);
     }
     return lists;
    }
}