102. 二叉树的层序遍历

题目：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

代码：

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //定义一个队列来存储每一层的数据
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //处理第n层
            List<Integer> level = new ArrayList<>();
            //第n层数据个数，即需要处理的个数
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }

}

使用二叉树BFS广度优先搜索实现，其实层序遍历就是广度优先搜索，参考：二叉树DFS深度优先搜索和BFS广度优先搜索区别动图

思路：利用队列先进先出的原理，遍历每一层的节点，在遍历时将下一层的节点存到队列中，通过记录每一层队列的数量来实现分层。具体实现逻辑参考代码。

使用二叉树DFS深度优先搜索实现的版本：

class Solution {

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

    private void handle(TreeNode node, List<List<Integer>> res, int level) {
        if (node == null) {
            return;
        }
        if (res.size() <= level) {
            //新的一层
            res.add(new ArrayList<>());
        }
        //获取当前层的list
        List<Integer> list = res.get(level);
        list.add(node.val);
        //递归调用子节点
        this.handle(node.left, res, level + 1);
        this.handle(node.right, res, level + 1);
    }

}

通过平台测试，DFS方式还更快1秒。实现思路：通过传参的形式，将层级这一信息进行传递，其他的就是遍历，没有什么区别。