[数据结构与算法]leetcode广度优先算法相似题

?1.二叉树的层次遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

思路：要做这一题首先了解广度优先算法（代码1），该算法能够按层依次从左到右遍历，使用的是队列，先进先出的特点。但是这一题是要求将每一层区分开，因此可以用一个n来记录该层的个数，再用for循环一次遍历一层的，遍历完一层的同时，将该层的删除，并且把每个节点的左右加入进去，变成下一层。每次for遍历的时候，队列中，只会有本层的节点。

//代码1
void BFS(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); 
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

//代码2，本题答案
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)
            return new ArrayList<List<Integer>>();
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        Queue<TreeNode> deque=new ArrayDeque<>();
        deque.add(root);
        while(!deque.isEmpty()){
            int n=deque.size();
            List<Integer> li=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode node=deque.poll();              
                li.add(node.val);
                if(node.left!=null)
                    deque.add(node.left);
                if(node.right!=null)
                    deque.add(node.right);
            } 

            list.add(li);
        }
        return list;
    }
}

2.二叉树的层次遍历 II
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/?

思想：和第一题很相似，只是顺序相反，就是再加入list集合时，插入到下标为0处

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null)
            return new ArrayList<List<Integer>>();
            List list=new ArrayList<List<Integer>>();
            Queue<TreeNode> queue=new ArrayDeque<>();

            queue.add(root);
            while(queue.isEmpty()!=true){
                List<Integer> li=new ArrayList<>();
                int n=queue.size();
                for(int i=0;i<n;i++){
                    TreeNode node=queue.poll();
                    li.add(node.val);
                    if(node.left!=null)
                        queue.add(node.left);
                   if(node.right!=null)
                        queue.add(node.right);
                }
                list.add(0,li);//每次都在0，就和第一题相反顺序了
            }

            return list;
    }
}

3.二叉树的锯齿形层次遍历?

?思想：这个将内部的list的顺序交换就行了，设置一个tag为标志，奇数层就从左到右，偶数相反。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        if(root==null)
            return list;       
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);
        int tag=0;
        while(!queue.isEmpty()){
            List<Integer> li=new ArrayList<>();
            int n=queue.size();
            tag++;
            for(int i=0;i<n;i++){        //这里判断插入
                TreeNode node=queue.poll();
                if(tag%2!=0)
                    li.add(node.val);
                else
                    li.add(0,node.val);
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(li);
        }
        return list;
    }
}

?4.二叉树的右视图

https://leetcode-cn.com/problems/binary-tree-right-side-view/

?思想：从右向左看的第一个，有可能在右边，也有可能在左边（右子树为null），但是每一层只会有一个，而且是最右的那个。这样，用广度优先将树按层来遍历，最后一个就加入list中。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list=new ArrayList<Integer>();
        if(root==null)
            return list;
        
        Queue<TreeNode> queue=new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int n=queue.size();
            TreeNode node =null;     
            for(int i=0;i<n;i++){
                node= queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
            }
            list.add(node.val);    //for遍历到了最后一个，加进去
        }
        return list;
    }
}