102. Binary Tree Level Order Traversal

栈。注意List的用法，比如有时候用deque，有时候用linkedlist。queue的时候一般用offer方法，因为容量满的时候不会抛出异常而是返回false。

public List<List<Integer>> levelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<>();
    if (root == null) return res;

    q.offer(root);

    while (!q.isEmpty()) {
        int levelNum = q.size();
        List<Integer> subRes = new LinkedList<>();
        for (int i = 0; i < levelNum; i++) {
            TreeNode node = q.poll();
            if (node.left != null)  q.offer(node.left);
            if (node.right != null) q.offer(node.right);
            subRes.add(node.val);
        }
        res.add(subRes);
        // res.add(0, subRes); // reverse the order of subRes for leetcode #107
    }
    return res;
}

dfs利用树的后序遍历：

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

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

// example
// [3,9,20,2,1,15,7]

// [[], [], [2]]
// [[], [], [2, 1]]
// [[], [9], [2, 1]]
// [[], [9], [2, 1, 15]]
// [[], [9], [2, 1, 15, 7]]
// [[], [9, 20], [2, 1, 15, 7]]
// [[3], [9, 20], [2, 1, 15, 7]]

107倒序只要换成:

if (level >= res.size()) res.add(0, new LinkedList<>());
res.get(res.size() - 1 - level, 0);