Binary Tree Level Order Traversal

Q：
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

A：
 ---------------简单的dfs， 每当看见一个节点，就加到结果上-----------------

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        int height = getHeight(root);
        for(int i =0;i<height;i++){
            all.add(new ArrayList<Integer>());
        }
        dfs(all,root,0);
        return all;
    }
    private void dfs(List<List<Integer>> all, TreeNode root, int level){
        if(root == null)
            return;
        all.get(level).add(root.val);
        dfs(all,root.left,level+1);
        dfs(all,root.right,level+1);
    }
    private int getHeight(TreeNode root){
        if(root == null)
            return 0;
        else
            return 1+Math.max(getHeight(root.left),getHeight(root.right));
    }
}

----------------------------第二遍，-------每次取下来一层，   放到一个Node 的list里，  同时保留Integer的一层---------------------

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> all = new LinkedList();
        if(root == null)
            return all;
        List<TreeNode> lastLevel = new LinkedList();
        List<Integer> l = new LinkedList();
        lastLevel.add(root);
        l.add(root.val);
        all.add(l);
        while(lastLevel.isEmpty() ==false){
            l = new LinkedList();
            List<TreeNode> newLevel = new LinkedList();
            for(TreeNode node:lastLevel){
                if( node.left !=null ){
                    newLevel.add(node.left);
                    l.add(node.left.val);
                }
                if( node.right !=null){
                    newLevel.add(node.right);
                    l.add(node.right.val);
                }
            }
            lastLevel = newLevel;
            if(l.isEmpty()==false)
                all.add(l);
        }
        return all;
    }
}

Mistakes:
 1: 考虑到 stack的特性， 我们在加入的时候，要先push right child ,then left
 2  艹～～～～～～～～～  BFS 是用Queue， 而不是stack， TNND
 3：  每次要在while里重新new一个List， 单纯的clear（）的话， ----由于其指针特性，会把all里的结果都clear掉
Learned:
1:   经常出现错误说“cannot create a generic array of .......”

Because of how generics in Java work, you cannot directly create an array of a generic type (such as Map<String, Object>[]). Instead, you create an array of the raw type (Map[]) and cast it to Map<String, Object>[]. This will cause an unavoidable (but suppressible) compiler warning. This should work for what you need: Map<String, Object>[] myArray = (Map<String, Object>[]) new Map[10]; You may want to annotate the method this occurs in with @SupressWarnings("unchecked"), to prevent the warning from being shown.

还有一个办法，就是  在new 的时候，不加generic type， 例如： 直接也不进行上面的cast
        Stack<TreeNode>[] twoStack = new Stack[2];

3： Queue is an Interface not a class. ，  so,we cannot use them as class.
Instead, we need use LinkedList or PriorityQueue and etc to simulate it.