树的层序遍历，层次遍历

题目链接-来源：力扣（LeetCode）

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回其层次遍历结果：

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

思路：

这里的层次遍历不同于常规的层序遍历，需要每一层返回一组输出结果。
也就是说，我们需要有某一种方法来记录当前所在的「深度」，或者记录当前行所需要打印的元素个数，以实现分批打印。
这里我使用了递归的辅助方法，记录当前进行的「深度」，当深度超过列表行数时，新建列表，否则将元素插入当前最后一行列表的末尾。
较简单的实现，可以在每一行打印开始前统计队列中元素个数，按此个数打印元素，即可省去每次都统计深度的麻烦。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        List<List<Integer>> ret = new ArrayList<>();
        if (root != null) {
            levelHelper(root, q, 0, ret);
        }
        return ret;
    }
    private void levelHelper(TreeNode t, Queue<TreeNode> q, int lvl, List<List<Integer>> ret) {
        q.offer(t);
        TreeNode cur = q.poll();
        if (lvl < ret.size()) {
            ret.get(lvl).add(cur.val);
        } else {
            List<Integer> l = new LinkedList<>();
            l.add(cur.val);
            ret.add(l);
        }
        if (cur.left != null) {
            levelHelper(cur.left, q, lvl + 1, ret);
        }
        if (cur.right != null) {
            levelHelper(cur.right, q, lvl + 1, ret);
        }
    }
}