leetcode hot 100

二叉树层序遍历

在本题中，是需要实现二叉树的广度遍历，即按照每一层遍历。这时候，我们就需要依靠队列来进行数据记录。同时队列在记录数据的过程中，统计队列的大小，作为当前层的元素个数，然后按照大小的值往外弹出元素。

比如，我首先把3放入队列，记录队列大小为1，然后把1弹出。然后把根节点的值3记录到数组中，然后判断3的左节点是不是空，不是的话把左节点也就是9加入队列，再判断3的右节点是不是空，不是的话把3的右节点也就是20加入队列。然后队列的长度减去1（因为我们弹出了一个元素，size是用来确定应该在队列中弹出几个元素的）

然后，我们进入下一次循环，此时size是0了,也就意味着第一层遍历完成了，把结果数组加入到一个二维数组中。

然后开始遍历第二层，因为队列中此时有9和20，长度为2，然后先把9弹出来，其左右节点都是空，长度减去1。

此时队列长度是1，意味着第二层还没遍历结束，那么再把20弹出，并判断其左右节点，然后长度减去1，变成0，意味着第二层遍历结束了，将第二层的数组加入到二维数组中。

然后队列中此时还有15 和 7，继续上述操作。

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();\\定义一个二维数组，用来存放结果，定义在这里是因为下面两个函数都需要调用！
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        checkFun(root);
        return result;
    }
    private void checkFun(TreeNode node){
        if(node == null) return;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(node);
        while(!queue.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int len = queue.size();
            while(len>0){
               TreeNode tempNode = queue.poll();
               itemList.add(tempNode.val);
               if(tempNode.left != null) queue.offer(tempNode.left);
               if(tempNode.right != null) queue.offer(tempNode.right);
               len--;
            }
            result.add(itemList);
        }
    }
}

本题中需要注意：
1.泛型的使用：二维数组定义的时候，泛型要给出
2.队列：queue，实际使用的是LinkedList，是链表，不是ArrayList，因为ArrayList底层是数组。
3.queue.offer()：add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！
4. queue.poll()：remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。