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

专栏：算法的魔法世界

个人主页：手握风云

目录

一、例题讲解

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 List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> ret = new ArrayList<>(); if (root == null) { return ret; } Queue<Node> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int n = queue.size(); List<Integer> 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<>(); if (root == null) { return ret; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int height = 1; while (!queue.isEmpty()) { int n = queue.size(); List<Integer> 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 来存储 Pair<TreeNode, 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) { List<Pair<TreeNode, Integer>> queue = new ArrayList<>(); int ret = 0; queue.add(new Pair(root, 1)); while (!queue.isEmpty()) { Pair<TreeNode, Integer> t1 = queue.get(0); Pair<TreeNode, Integer> t2 = queue.get(queue.size() - 1); ret = Math.max(ret, t2.getValue() - t1.getValue() + 1); List<Pair<TreeNode, Integer>> tmp = new ArrayList<>(); for (Pair<TreeNode, 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 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 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; } }