二叉树——102，107，199，637

前中后序遍历是二叉树的深度遍历，而层序遍历则是二叉树的广度遍历。顾名思义，二叉树的层序遍历就是一层一层遍历二叉树的每一个节点。今天的几道题都是关于二叉树的层序遍历的，大体思路都非常相似，都是在层序遍历的基础上实现了有着些许差异的不同。

LeetCode102.二叉树的层序遍历

第一道题是二叉树的层序遍历，这道题的要求是将每一层的先装入列表中，最后将所有列表在装入一个列表，返回该列表。
层序遍历的思路是借助一个队列，从二叉树的根节点开始，将该层所有节点入队后，开始出队，每出栈一个，将其左右节点入队，直到该层节点全部出队后，该层遍历结束，将这些节点按出队顺序加入列表，然后循环上述过程，开始下一层的遍历。

	public static List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null){
            return list;
        }else {
            queue.offer(root);
        }
        TreeNode node=root;
        while(!queue.isEmpty()){
            List<Integer> lst=new ArrayList<>();
            int count=queue.size();
            for (int i= 0;i<count;i++) {
                node=queue.peek();
                lst.add(queue.poll().val);
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null) {
                    queue.offer(node.right);
                }
            }
            list.add(lst);
        }
        return list;
    }

这里的需要注意的点是，首先要判断根节点是否为空，如果为空，说明二叉树没有节点，直接返回空列表。其次需要一个临时指针node，来指向队头元素，这样在该元素出队的时候，将其左右节点入队，入队时需要判断节点是否存在，如果不存在，则会报空指针异常的错误。这道题还需要一个计数器count，count在每次循环刚开始时，定义为队列的长度，这是因为循环刚开始队列的长度是这一层的节点数目，需要记下这个长度来将每一层的节点分开，分别存入不同的列表中。

LeetCode107.二叉树的层序遍历Ⅱ

这道题和前面的题类似，不过需要自底向上，刚刚是自顶向下，所以我们可以在刚刚代码的基础上，将最后的列表翻转即可。

	public static List<List<Integer>> levelOrderBottom(TreeNode root){
        List<List<Integer>> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null){
            return list;
        }else {
            queue.offer(root);
        }
        TreeNode node=root;
        while(!queue.isEmpty()){
            List<Integer> lst=new ArrayList<>();
            int count=queue.size();
            for (int i= 0;i<count;i++) {
                node=queue.peek();
                lst.add(queue.poll().val);
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null) {
                    queue.offer(node.right);
                }
            }
            list.add(lst);
        }
        Collections.reverse(list);
        return list;

LeetCode199.二叉树的右视图

这道题需要找到二叉树每一层最右边的元素，我们可以在层序遍历的基础上，返回每一层最后一个元素。

	public static List<Integer> rightSideView(TreeNode root){
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return list;
        }else {
            queue.offer(root);
        }
        TreeNode node=root;
        while (!queue.isEmpty()){
            int size= queue.size();
            for (int i = 0; i < size; i++) {
                node=queue.peek();
                if (i==size-1){
                    list.add(node.val);
                }
                queue.poll();
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
        return list;
    }

LeetCode637.二叉树的层平均值

本题需要求层平均值，可以在遍历每层时，将每个节点的值相加，最后遍历完一层后求平均值即可。

	public static List<Double> averageOfLevels(TreeNode root){
        List<Double> list=new ArrayList<>();
        Queue<TreeNode> queue =new LinkedList<>();
        if (root==null){
            return list;
        }else {
            queue.offer(root);
        }
        TreeNode node;
        while(!queue.isEmpty()){
            int size=queue.size();
            double sum=0;
            for (int i = 0; i < size; i++) {
                node=queue.poll();
                sum=sum+node.val;
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
            }
            list.add(sum/size);
        }
        return list;
    }