优选算法的层序之径：队列专题

专栏算法的魔法世界个人主页手握风云目录一、例题讲解1.1. N 叉树的层序遍历1.2. 二叉树的锯齿形层序遍历1.3. 二叉树最大宽度1.4. 在每个树行中找最大值一、例题讲解1.1. N 叉树的层序遍历题目要求给定一棵 N 叉树需要返回该树节点值的层序遍历结果层序遍历需遵循从左到右、逐层遍历的规则。本题我们需要借助队列先把根节点放入队列中接着使用 while 循环先统计队列里的元素个数借助 for 循环将队头元素出队列这样就可以将每一层的元素全部出队列将其孩子节点加入到队列中而下一层的节点又被全部加入队列。/* // Definition for a Node. class Node { public int val; public ListNode children; public Node() {} public Node(int _val) { val _val; } public Node(int _val, ListNode _children) { val _val; children _children; } }; */ class Solution { public ListListInteger levelOrder(Node root) { ListListInteger ret new ArrayList(); if (root null) { return ret; } QueueNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int n queue.size(); ListInteger curLevel new ArrayList(); for (int i 0; i n; i) { Node node queue.poll(); curLevel.add(node.val); for (Node x : node.children) { queue.offer(x); } } ret.add(curLevel); } return ret; } }1.2. 二叉树的锯齿形层序遍历本题要求实现二叉树的锯齿形层序遍历给定二叉树的根节点 root需返回其节点值按照锯齿形规则遍历后的结果具体遍历规则为逐层遍历二叉树第一层从左往右遍历节点第二层从右往左遍历后续每一层均与上一层的遍历方向交替切换。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger ret new ArrayList(); if (root null) { return ret; } QueueTreeNode queue new LinkedList(); queue.offer(root); int height 1; while (!queue.isEmpty()) { int n queue.size(); ListInteger curLevel new ArrayList(); for (int i 0; i n; i) { TreeNode node queue.poll(); curLevel.add(node.val); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } if (height % 2 0) { Collections.reverse(curLevel); } height; ret.add(curLevel); } return ret; } }1.3. 二叉树最大宽度要求给定一棵二叉树的根节点 root计算并返回该二叉树的最大宽度。其中树的最大宽度为所有层中宽度的最大值每一层的宽度定义为该层最左侧与最右侧的非空节点之间的长度计算时需把该二叉树看作结构一致的满二叉树。我们这里利用二叉树的顺序实现假设根节点的下标为1那么其左孩子节点下标为2 * 1其右孩子节点下标为2 * 1 1。这次的队列不光需要存节点的地址还需要存下标这时我们可以使用 Pair 来存储 PairTreeNode, Integer。我们从根节点开始把根节点的地址和下标一起入队列当根节点出队列的时候如果左孩子节点或者右孩子不为空则继续入队列。对于宽度的计算我们只需要取出队头和队尾的元素的节点下标相减即可得到。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public int widthOfBinaryTree(TreeNode root) { ListPairTreeNode, Integer queue new ArrayList(); int ret 0; queue.add(new Pair(root, 1)); while (!queue.isEmpty()) { PairTreeNode, Integer t1 queue.get(0); PairTreeNode, Integer t2 queue.get(queue.size() - 1); ret Math.max(ret, t2.getValue() - t1.getValue() 1); ListPairTreeNode, Integer tmp new ArrayList(); for (PairTreeNode, Integer t : queue) { TreeNode node t.getKey(); int index t.getValue(); if (node.left ! null) { tmp.add(new Pair(node.left, index * 2)); } if (node.right ! null) { tmp.add(new Pair(node.right, index * 2 1)); } } queue tmp; } return ret; } }1.4. 在每个树行中找最大值这道题要求给定一棵二叉树的根节点root需要找出该二叉树每一层节点中的最大值并将每一层的最大值按层级顺序整理成列表返回。本道题我们依然采用宽搜的思想在每一层进行遍历的时候定义一个变量与每一个节点值进行比较并更新。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public ListInteger largestValues(TreeNode root) { ListInteger ret new ArrayList(); if (root null) { return ret; } QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int len queue.size(); int maxLevel Integer.MIN_VALUE; for (int i 0; i len; i) { TreeNode node queue.poll(); maxLevel Math.max(maxLevel, node.val); if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } ret.add(maxLevel); } return ret; } }