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的思想考慮的話，它會把樹的每層最左邊節(jié)點存成一個cell list放到res里去，然后再backtracking回來，拿到那一level的節(jié)點繼續(xù)往響應(yīng)的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保存結(jié)點。

Code Ganker的講解太好了：
這道題要求實現(xiàn)樹的層序遍歷，其實本質(zhì)就是把樹看成一個有向圖，然后進(jìn)行一次廣度優(yōu)先搜索，這個圖遍歷算法是非常常見的，這里同樣是維護(hù)一個隊列，只是對于每個結(jié)點我們知道它的鄰接點只有可能是左孩子和右孩子，具體就不仔細(xì)介紹了。算法的復(fù)雜度是就結(jié)點的數(shù)量，O(n)，空間復(fù)雜度是一層的結(jié)點數(shù)，也是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);
        //本層結(jié)點數(shù)
        int curNum = 1;
        //下一層結(jié)點數(shù)
        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循環(huán)里，否則會出現(xiàn)下面的錯誤。

Input:

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

另外注意，queue要用poll方法取數(shù)而不是pop。