102. 二叉树的层序遍历

image.png

主要利用队列queue，queue的实现利用LinkedList
流程：
1：先将根节点加入queue，进行初始化
2：进行while循环，条件是queue不为空
3：得到每一层的节点数量，并进行for循环，遍历层中的每一个节点，如果该节点有左孩子，就加入queue，右孩子也类似
注意：队列中要存TreeNode，这样才能判断有没有左右子树，能保持这种联系

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> list=new ArrayList<>();
        if(root!=null) queue.add(root);//先将根节点加入，进行初始化
        while(!queue.isEmpty()){//一次循环就是去遍历一层的节点
            int n=queue.size();//n就是一层的节点数量
            List<Integer> list1=new ArrayList<>();//来装一层的数字
            for(int i=0;i<n;i++){
                TreeNode r=queue.poll();
                list1.add(r.val);//加入arraylist
                if(r.left!=null){//如果左子树不为空，就加入队列
                    queue.add(r.left);
                }
                if(r.right!=null){
                    queue.add(r.right);
                }
            }
            list.add(new ArrayList<Integer>(list1));
        }
        return list;
    }
}