Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

07/04/2017更新

前天周三，覃超说这题可以用DFS做。就做了一下。
精巧的地方在于res.get(level).add(node.val);这一句。按照DFS的思想考虑的话，它会把树的每层最左边节点存成一个cell list放到res里去，然后再backtracking回来，拿到那一level的节点继续往响应的leve 所在的cell list里面加。

如下：

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        dfs(res, root, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, TreeNode node, int level) {
        if (node == null) return;
        if (level >= res.size()) {
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(node.val);
        dfs(res, node.left, level + 1);
        dfs(res, node.right, level + 1);
    }

---

初版

这题跟求Maximum depth of a binary的非递归方法非常像，用一个queue保存结点。

Code Ganker的讲解太好了：
这道题要求实现树的层序遍历，其实本质就是把树看成一个有向图，然后进行一次广度优先搜索，这个图遍历算法是非常常见的，这里同样是维护一个队列，只是对于每个结点我们知道它的邻接点只有可能是左孩子和右孩子，具体就不仔细介绍了。算法的复杂度是就结点的数量，O(n)，空间复杂度是一层的结点数，也是O(n)。

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //本层结点数
        int curNum = 1;
        //下一层结点数
        int nextNum = 0;
        List<Integer> cell = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            curNum--;
            cell.add(temp.val);

            if (temp.left != null) {
                queue.add(temp.left);
                nextNum++;
            }
            if (temp.right != null) {
                queue.add(temp.right);
                nextNum++;
            }
            if (curNum == 0) {
                res.add(cell);
                curNum = nextNum;
                nextNum = 0;
                
                cell = new ArrayList<>();
            }
        }
        return res;
    }

注意不要把
List<Integer> cell = new ArrayList<>();写到while循环里，否则会出现下面的错误。

Input:

[3,9,20,null,null,15,7]
Output:
[[3],[20],[7]]
Expected:
[[3],[9,20],[15,7]]

另外注意，queue要用poll方法取数而不是pop。