二叉树的层次遍历

题目描述：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

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

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

Java代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    //在使用广度优先搜索时，增加level表示房当前遍历到二叉树的哪一层，size表示在当前遍历层有多少个元素
    //把这些元素遍历完就相当于向外走了一步
    //使用队列保存每层的所有节点，每次把队列里原先的元素进行出队列操作，再把每个元素的非空左右节点
    //送入队列，然后得到每层的遍历
    public List<List<Integer>> levelOrderBFS(TreeNode root) {
        List<List<Integer>> res =  new ArrayList<>();
        Queue<TreeNode> dq = new LinkedList<>();
        dq.offer(root);

        while(!dq.isEmpty()) {
            int size = dq.size();
            List<Integer> level = new LinkedList<>();
            for(int i = 0;i < size;i++) {
                TreeNode cur = dq.peek();
                dq.poll();
                if(cur == null) continue;
                level.add(cur.val);
                dq.offer(cur.left);
                dq.offer(cur.right);
            }
            if(!level.isEmpty()) res.add(level);
        }

        return res;
    }
    
    //DFS不是按照层次遍历的，为了让递归过程中同一层的节点放入同一个列表中，在每次递归时要记录每个节点的
    //深度level，在递归到新节点时要把该节点放入level的末尾
    //当遍历到一个新的深度level时，如果res中还没有创建level对应的列表时，应在res中新建一个列表来保存
    //该level的所有节点
    public List<List<Integer>> levelOrderDFS(TreeNode root) {
        List<List<Integer>> res =  new ArrayList<>();
        if(root != null) dfs(res, root, 0);
        return res;
    }

    private void dfs(List<List<Integer>> res, TreeNode node, int level) {
        if(res.size() - 1 < level) res.add(new ArrayList<>());

        res.get(level).add(node.val);

        if(node.left != null) dfs(res, node.left, level + 1);

        if(node.right != null) dfs(res, node.right, level + 1);
    } 
}