系统学习算法 专题十八 队列+宽搜

题目一：

算法原理：

层序遍历是经典的宽搜，即BFS搜索方式，往往和队列搭配使用

这道题的步骤为，先将头结点放进队列，然后去遍历此时队列中所有的元素，然后在遍历队列的过程中，又将被遍历的元素的所有子节点全部加进队列，当此次遍历结束后，就会将下一层的元素全部放进队列中，然后将本次遍历的所有元素放进一个顺序表中，再加入返回顺序表中即可

代码：

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        //结果集
        List<List<Integer>> ret=new ArrayList<>();
        //特判
        if(root==null){
            return ret;
        }
        //添加根结点
        Queue<Node> q=new LinkedList<>();
        q.offer(root);
        //宽搜
        while(!q.isEmpty()){
            int sz=q.size();
            List<Integer> list=new ArrayList<>();
            //遍历本层的所有元素
            for(int i=0;i<sz;i++){
                Node t=q.poll();
                list.add(t.val);
                //将下一层元素放进队列
                for(Node child:t.children){
                    if(child!=null){
                        q.offer(child);
                    }
                }
            }
            //将本层元素存进一个顺序表中并放进结果集
            ret.add(list);
        }
        //返回结果
        return ret;
    }
}

题目二：

算法原理：

题意很简单，跟层序遍历差不多，只是变成了左右交替的顺序进行层序遍历，因此需要一个标记位来记录本层的遍历顺序是从左往右还是从右往左的，如果是从右往左，则在原来的层序遍历的基础上，添加一个逆序操作即可

代码：

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //结果集
        List<List<Integer>> ret=new ArrayList<>();
        //特判
        if(root==null){
            return ret;
        }
        Queue<TreeNode> q=new LinkedList<>();
        //记录本次是往左还是往右
        int flag=0;
        q.offer(root);
        //宽搜
        while(!q.isEmpty()){
            int sz=q.size();
            List<Integer> list=new ArrayList<>();
            //遍历本层元素
            for(int i=0;i<sz;i++){
                TreeNode node=q.poll();
                list.add(node.val);
                //将下一层元素放进队列
                if(node.left!=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            //如果是从右往左的
            if(flag==1){
                //逆序
                Collections.reverse(list);
                flag=0;
            }else{
                flag=1;
            }
            //将本层元素放进顺序表并加入到结果集
            ret.add(list);
        }
        return ret;
    }
}

题目三：

算法原理：

这道题题意有一点困难，首先需要注意的是，这棵树是当作满二叉树看的，即虽然空结点没有显示，但也算作一个结点，并计入该层的长度，然后就是每一层的长度，不能简单的直接套用满二叉树每一层的长度公式，因为题目要求的每层长度是指从最左到最右的非空结点之间的长度

第一反应肯定是暴力，即采用层序遍历，然后将所有结点都扔进去，包括空结点，每次遍历一层后，就统计一下该层的长度，当层序遍历结束后，答案也就出来了

理论可行，但是会空间溢出，因为空间太大了，比如这一层有值的结点只有最左边的一个结点，和最右边的一个结点，当高度足够大的时候，中间要存的空结点足够多，而且每往下遍历一层，空间开销都是呈指数级增长的

这时解决这个问题，就需要利用二叉树的相关公式，即父子孩子的下标计算，即如果父结点的下标为x，那么其左孩子的下标为2x，右孩子的下标为2x+1

所有根据这个公式，根本不需要存储空结点，只需要将最右有值结点的下标减去最左有值结点的下标再加1即可

比如这颗树，计算第四层的长度，就直接通过15-8+1=7即可计算出这一层的长度

这样解决了空间开销溢出，但是会出现下标溢出的情况

因为是二叉树，当树的高度假设为1000，那么最右的结点下标就为2^1000，就会出现超出整数类型的最大值，造成溢出，当溢出后就会变为负数

假设最右结点的下标溢出后为-126，最左结点的下标没有溢出为127，那么套用公式则为-126-127+1=-252，但是明明长度应该是127+3溢出后为-126，长度明明是4

其实Java系统中计算不是这样计算的，而是会进行求模，即表明上是-126-127=-253，但其实还要再模256，即-253%256=3，即-126-127=3

又因为题目说了答案将会在32位带符号整数范围内，所以不可能使得两个结点的差值超过一圈，所以即使溢出也不会造成答案错误

代码：

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        //用数组模拟队列
        List<Pair<TreeNode,Integer>> q=new ArrayList<>();
        //添加头结点
        q.add(new Pair<TreeNode,Integer>(root,1));
        //结果
        int ret=0;
        //宽搜
        while(!q.isEmpty()){
            //更新长度
            Pair<TreeNode,Integer> t1=q.get(0);
            Pair<TreeNode,Integer> t2=q.get(q.size()-1);
            ret=Math.max(t2.getValue()-t1.getValue()+1,ret);
            //下一层的结点
            List<Pair<TreeNode,Integer>> tmp=new ArrayList<>();
            for(Pair<TreeNode,Integer> t:q){
                TreeNode node=t.getKey();
                int index=t.getValue();
                if(node.left!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.left,2*index));
                }
                if(node.right!=null){
                    tmp.add(new Pair<TreeNode,Integer>(node.right,2*index+1));
                }
            }
            //更新队列
            q=tmp;
        }
        //返回结果
        return ret;
    }
}

其中Pair是一个键值对的数据结构，类似于哈希表

题目四：

算法原理：

题意很简单，就是找出每层结点中的最大值，并存进数组中，直接用层序遍历即可

代码：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        //结果集
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> q=new LinkedList<>();
        //特判
        if(root==null){
            return list;
        }
        //添加头结点
        q.offer(root);
        //层序遍历
        while(!q.isEmpty()){
            int size=q.size();
            int max=Integer.MIN_VALUE;
            for(int i=0;i<size;i++){
                TreeNode node=q.poll();
                //找最大值
                max=Math.max(max,node.val);
                if(node.left!=null){
                    q.offer(node.left);
                }
                if(node.right!=null){
                    q.offer(node.right);
                }
            }
            //将这一层的最大值添加到结果集
            list.add(max);
        }
        //返回结果集
        return list;
    }
}