题解 | #求二叉树的层序遍历# 队列来完成层次遍历

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /*
        解题思路：利用队列来添加每一层节点。
            如：首先将根节点3添加到队列。 （此时队列中只有3）
            然后，只要队列不为空，则循环出队。
            出队时有个技巧。需要先获取住队列的大小,然后再循环把当前存在的元素依依出队添加到结果集中。
            同时添加它的左右子节点到队列中。
            程序流程如下：
            队列：{3}
            出队：出3元素，同时3的左右子节点到队列。 结果集：{3}
            
            队列：{9，20}
            出队：出9，出20，同时把9、20的左右子树添加队列。结果集：{3，9，20}
            
            队列：{15，7}
            出队：出15，出7，同时把15、7的左右子树添加队列。结果集：{3，9，20，15，7}
            
            循环(队列不为空){
               获取队列大小。
               循环出当前存在的元素。出一个元素添加到结果集，同时将它的左右子树添加到的队列中。
            }
            
            
    */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
         if(root == null) return res;
        // 层次遍历，利用队列完成
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
           ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        // 程序能执行到此处，说明已经层次遍历结束
        return res;
    }
}