【算法】【优选算法】宽搜（BFS）中队列的使用

目录

• 一、429. N叉树的层序遍历
• 二、103.⼆叉树的锯⻮形层序遍历
• 三、662.⼆叉树最⼤宽度
• 四、515.在每个树⾏中找最⼤值

一、429. N叉树的层序遍历

题目链接：429.N叉树的层序遍历
题目描述：

题目解析：

• 层序遍历N叉树，每一层的节点是由null分开
• 每一层节点的val值放入一个数组中，最后返回一个二维数组，每行就是对应层数据

解题思路：

• 我们将每一层的节点放入一个队列中，每次队列出节点的时候就将这个节点的孩子节点入队
• 因为节点数范围是包含0的，所有当根节点为null时，返回空二维数组
• 因为出队列伴随着入队，所以要区分每层节点，在出该层队列中节点前，先求一下长度，然后出这个长度对应节点个数即可。
• 在入队列的时候，因为使用null区分，所以要将null节点排除不入队列。

解题代码：

//时间复杂度：O(n)//空间复杂度：O(n)class Solution { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> ret = new ArrayList<>(); if(root == null) return ret;//节点数为0 Queue<Node> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { int sz = queue.size();//每层节点个数 List<Integer> tmp = new ArrayList<>();//每层节点//下一层节点 for(int i = 0; i < sz; i++) { Node node = queue.poll(); tmp.add(node.val); for(Node x : node.children) {  if(x != null) { queue.offer(x);  } } } ret.add(tmp); } return ret; }}

二、103.⼆叉树的锯⻮形层序遍历

题目链接：103.⼆叉树的锯⻮形层序遍历
题目描述：

题目解析：

• 层序遍历二叉树，每一层节点的val值放入一个数组中，根节点为第一层，奇数层顺序放入，偶数层逆序放入，最后返回一个二维数组，每行就是对应层数据

解题思路：

• 我们将每一层的节点放入一个队列中，每次队列出节点的时候就将这个节点的孩子节点入队
• 因为节点数范围是包含0的，所有当根节点为null时，返回空二维数组
• 因为出队列伴随着入队，所以要区分每层节点，在出该层队列中节点前，先求一下长度，然后出这个长度对应节点个数即可。
• 在入队列的时候，因为使用null区分，所以要将null节点排除不入队列。
• 使用一个变量标记一下当前的层数，最后一维数组入结果数组是，如果是偶数层数就逆序。

解题代码：

//时间复杂度：O(n)//空间复杂度：O(n)class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<>(); if(root == null) return ret;//节点数为0 Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int level = 1;//层 //入队列，出队列 while(!queue.isEmpty()) { int sz = queue.size(); List<Integer> tmp = new ArrayList<>(); for(int i = 0; i < sz; i++) { TreeNode node = queue.poll(); tmp.add(node.val); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } //偶层数 逆序 if(level % 2 == 0) Collections.reverse(tmp); ret.add(tmp); level++; } return ret; }}

三、662.⼆叉树最⼤宽度

题目链接：662.⼆叉树最⼤宽度
题目描述：

题目解析：

• 求二叉树中每层的长度的最大值
• 每层的长度指：当前层第一个不是null的节点与最后一个不是null的节点之间 的 节点个数包含null节点
• 节点数不会是0个

解题思路：

• 我们直接将null节点填入，不仅麻烦还会超时。
• 所以我们将二叉树看成是数组存储的，将每个节点的下标给带上，与节点构成一个键值对，放入队列中。
• 因为我们要求长度：需要拿到每层节点第一个节点和最后一个节点的下标，那么队列不能满足需求，使用一个数组来模拟队列存储。
• 每次在下一层节点入队前，先拿到第一个节点和最后一个节点的下标，求程度与结果的较大值。
• 这个数组只存一层的数据，下一层我们使用一个临时数组来存储，最后赋值即可。
• 遍历数组，将下一层不为空的节点放入临时数组。

解题代码：

//时间复杂度：O(n)//空间复杂度：O(n)class Solution { public int widthOfBinaryTree(TreeNode root) { int ret = 0; List<Pair<TreeNode, Integer>> queue = new ArrayList<>();//数组只存每一层节点与对应坐标 queue.add(new Pair<>(root, 0));//根节点入队 while(!queue.isEmpty()) { //数组最后元素与第一个元素的value域，求当前层的长度 ret = Math.max(ret, queue.get(queue.size() - 1).getValue() - queue.get(0).getValue() + 1); //数组记录下一层节点 List<Pair<TreeNode, Integer>> tmp = new ArrayList<>(); for(Pair<TreeNode, Integer> node : queue) { if(node.getKey().left != null) tmp.add(new Pair<>(node.getKey().left, node.getValue() * 2 + 1)); if(node.getKey().right != null) tmp.add(new Pair<>(node.getKey().right, node.getValue() * 2 + 2)); } queue = tmp; } return ret; }}

四、515.在每个树⾏中找最⼤值

题目链接：515.在每个树⾏中找最⼤值
题目描述：

题目解析：

• 将二叉树中每层节点的value的最大值放入要返回的结果数组中
• value域的值范围是int的取值范围，包含负数的

解题思路：

• 我们将每一层的节点放入一个队列中，每次队列出节点的时候就将这个节点的孩子节点入队
• 因为节点数范围是包含0的，所有当根节点为null时，返回空数组
• 因为出队列伴随着入队，所以要区分每层节点，在出该层队列中节点前，先求一下长度，然后出这个长度对应节点个数即可。
• 在出队列前，先使用一个变量赋值为int的最小值，在每次出节点前，变量更新为该节点的value与变量的更大值。
• 在入队列的时候，要将null节点排除不入队列。

解题代码：

//时间复杂度：O(n)//空间复杂度：O(n)class Solution { public List<Integer> largestValues(TreeNode root) { List<Integer> ret = new ArrayList<>(); if(root == null) return ret; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()) { int sz = queue.size(); int max = Integer.MIN_VALUE; for(int i = 0; i < sz; i++) { TreeNode node = queue.poll(); max = Math.max(node.val, max); if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } ret.add(max); } return ret; }}