二叉树层序遍历

Leedcode 102

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

【1】输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

【2】输入：root = [1]  输出：[[1]]

【3】输入：root = [] 输出：[]

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑

层序遍历方式就是图论中的广度优先遍历，现在应用在二叉树上

public List> levelOrder(TreeNode root) {

    List> result =new ArrayList>();

    if (null == root){

        return result;

    }

    //Queue是先进先出的集合，常用于任务调度等场景

    Queue que =new LinkedList();

    que.offer(root);

    while (!que.isEmpty()){

        List valList =new ArrayList();

        int len = que.size();

        while (len>0){

            TreeNode curNode = que.poll();

            valList.add(curNode.val);

            if (null != curNode.left ) que.offer(curNode.left);

            if (null != curNode.right) que.offer(curNode.right);

            len--;

        }

        result.add(valList);

    }

    return result;

}