网站维护和建设实报告,万网官网,建设网站的硬件,企业网站建设 调研二叉树的层次遍历经典问题-算法通关村 1 层次遍历简介 广度优先在面试里出现的频率非常高#xff0c;整体属于简单题。广度优先又叫层次遍历#xff0c;基本过程如下#xff1a; 层次遍历就是从根节点开始#xff0c;先访问根节点下面一层全部元素#xff0c;再访问之后…二叉树的层次遍历经典问题-算法通关村 1 层次遍历简介 广度优先在面试里出现的频率非常高整体属于简单题。广度优先又叫层次遍历基本过程如下 层次遍历就是从根节点开始先访问根节点下面一层全部元素再访问之后的层次类似金字塔一样一层层访问。我们可以看到这里就是从左到右一层一层的去遍历二叉树先访问3之后访问3的左右子孩子9和20之后分别访问9和20的左右子孩子8,13和1517最后得到结果 3,9,20,8,13,15,17。 这里的问题是怎么将遍历过的元素的子孩子保存一下呢例如访问9时其左右子孩子8和13应该先存一下直到处理20之后才会处理。使用队列来存储能完美解决上述问题例如上面的图中 1. 首先3入队 2.然后3出队之后将3的左右孩子9和20保存到队列中。 3.之后9出队将9的左右孩子8和13入队。 4.之后20出队将20的左右孩子15和7入队。 5.之后 8,13,15,7分别出队此时都是叶子结点只出队就行。 这就是LeetCode里经典的层次遍历题102.二叉树的层序遍历107.二叉树的层次遍历II199.二叉树的右视图637.二叉树的层平均值429.N叉树的前序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II103 锯齿层序遍历 除此之外在深度优先的题目里有些仍然会考虑层次遍历的实现方法。 2 基本的层序遍历与变换 仅仅遍历并输出全部元素 public ListInteger simpleLevelOrder(TreeNode root){if(root null){return new ArrayListInteger();}ListInteger list new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);while(!TreeQueue.isEmpty()){//一层一层的遍历for(int i 0; i TreeQueue.size(); i){TreeNode temp TreeQueue.poll();list.add(temp.val);if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}}return list;}2.1二叉树的层序遍历 LeetCode102给你一个二叉树请你返回其按层次遍历得到的节点值。即逐层地从左到右访问所有节点。 如何判断某一层访问完了呢简单用一个变量size标记一下就行了size表示某一层的元素个数只要出队就将size减1减到O就说明该层元素访问完了。当size变成0之后这时队列中剩余元素的个数恰好就是下一层元素的个数因此重新将size标记为下一层的元素个数就可以继续处理新的一行了。最后把每层遍历到的节点都放到一个结果集中将其返回就行了。 public ListListInteger levelOrder(TreeNode root){if(root null){return new ArrayListListInteger();}ListListInteger res new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);while(!TreeQueue.isEmpty()){//存储每一层的元素ListInteger list new ArrayList();for(int i 0; i TreeQueue.size(); i){TreeNode temp TreeQueue.poll();list.add(temp.val);if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}res.add(list);}return res;}2.2 层序遍历-自底向上 LeetCode 107.给定一个二叉树返回其节点值自底向上的层序遍历。即按从叶子节点所在层到根节点所在的层逐层从左向右遍历。例如给定的二叉树为 [ [15, 7], [9, 20], [3] ] 如果要求从上到下输出每一层的节点值做法是很直观的在遍历完一层节点之后将存储该层节点值的列表添加到结果列表的尾部。这道题要求从下到上输出每一层的节点值只要对上述操作稍作修改即可在遍历完一层节点之后将存储该层节点值的列表添加到结果列表的头部。 public ListListInteger levelOrderBottom(TreeNode root){if(root null){return new ArrayListListInteger();}ListListInteger res new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);while(!TreeQueue.isEmpty()){//存储每一层的元素ListInteger levelList new ArrayList();for(int i 0; i TreeQueue.size(); i){TreeNode temp TreeQueue.poll();levelList.add(temp.val);if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}//当前层的节点值列表 levelList 添加到结果列表 res 的开头// 实现了层次遍历结果的逆序存储。res.add(0, levelList);}return res;}2.3二叉树的锯齿形层序遍历 LeetCode103 给定一个二叉树返回其节点值的锯齿形层序遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 例如给定二叉树 3,9,20,null,null,15,7 [ [3], [20, 9] [15, 7] ] 这个题也是102的变种只是最后输出的要求有所变化要求我们按层数的奇偶来决定每一层的输出顺序。如果当前层数是偶数从左至右输出当前层的节点值否则从右至左输出当前层的节点值。 我们依然可以沿用第102题的思想为了满足题目要求的返回值为**「先从左往右再从右往左」交替输出的锯齿形可以利用「双端队列」**的数据结构来维护当前层节点值输出的顺序。双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展但是对当前层节点的存储我们维护一个变量isOrderLeft 记录是从左至右还是从右至左的 • 如果从左至右我们每次将被遍历到的元素插入至双端队列的末尾。 •从右至左我们每次将被遍历到的元素插入至双端队列的头部。 public ListListInteger zigzagLevelOrder(TreeNode root){if(root null){return new ArrayListListInteger();}ListListInteger res new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);boolean isOrderLeft true;while(!TreeQueue.isEmpty()){//存储每一层的元素DequeInteger levelQueue new ArrayDeque();for(int i 0; i TreeQueue.size(); i){TreeNode temp TreeQueue.poll();if(isOrderLeft){levelQueue.addLast(temp.val);}else{levelQueue.addFirst(temp.val);}if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}res.add(new ArrayListInteger(levelQueue));isOrderLeft !isOrderLeft;}return res;}2.4 N 叉树的层序遍历 LeetCode429 给定一个 N 叉树返回其节点值的层序遍历。即从左到右逐层遍历。树的序列化输入是用层序遍历每组子节点都由 null值分隔参见示例。 输入root [ 1, null, 3, 2, 4, null, 5, 6]表述树的元素是这个序列 输出[ [1] [3,2,4][5,61] ] N 叉树的定义如下就是一个值加一个列表。 public class Node {public int val;public ListNode children;}public ListListInteger nLevelOrder(Node root){if(root null){return new ArrayListListInteger();}ListListInteger res new ArrayList();DequeNode NTreeQueue new ArrayDeque();NTreeQueue.offer(root);while(!NTreeQueue.isEmpty()){ListInteger levelList new ArrayList();while(!NTreeQueue.isEmpty()){Node cur NTreeQueue.pollFirst();levelList.add(cur.val);for (Node child : cur.children) {if(child ! null){NTreeQueue.add(child);}}}res.add(levelList);}return res;}3 几个处理每层元素的项目
LeetCode三道题目515.在每个树行中找最大值最小637.二叉树的层平均值199.二叉树的右视图。
3.1 在每个树行中找最大值 LeetCode515: 给定一棵二叉树的根节点 root请找出该二叉树中每一层的最大值。 在得到一层的元素之后用一个变量记录其最大值。 public ListInteger largestValues(TreeNode root){if(root null){return new ArrayListInteger();}ListInteger res new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);while(!TreeQueue.isEmpty()){//存储每一层的元素int levelMaxNum Integer.MIN_VALUE;for(int i 0; i TreeQueue.size(); i){TreeNode temp TreeQueue.poll();levelMaxNum Math.max(levelMaxNum, temp.val);if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}res.add(levelMaxNum);}return res;}3.2 在每个树行中找平均值 LeetCode637要求给定一个非空二叉树返回一个由每层节点平均值组成的数组。 将每层的元素都先保存下来最后求平均值。 public ListDouble averageOfLevels(TreeNode root){if(root null){return new ArrayListDouble();}ListDouble res new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);while(!TreeQueue.isEmpty()){double levelAverage 0;int len TreeQueue.size();for(int i 0; i len; i){TreeNode temp TreeQueue.poll();levelAverage temp.val;if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}res.add(levelAverage/len);}return res;}3.3 二叉树的右视图 LeetCode 199给定一个二叉树的根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。例如 利用BFS进行层次遍历记录下每层的最后一个元素。 public ListInteger rightSideView(TreeNode root){if(root null){return new ArrayListInteger();}ListInteger res new ArrayList();DequeTreeNode TreeQueue new ArrayDeque();//将根节点放入队列中然后不断遍历TreeQueue.offer(root);while(!TreeQueue.isEmpty()){int len TreeQueue.size();int rightValue 0;for(int i 0; i len; i){TreeNode temp TreeQueue.poll();if(i len-1){rightValue temp.val;}if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}res.add(rightValue);}return res;}3.4 最底层最左边 LeetCode513: 给定一个二叉树的 根节点root请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例1输入root [2, 1, 3] 输出1示例2输入[1, 2, 3, 4, null, 5, 6, null, null, 7] 输出7 这里有两个问题该怎么知道什么时候到了最底层呢假如最底层有两个该怎么知道哪个是最左的呢我们继续观察层次遍历的执行过程 我们可以发现正常执行层次遍历不管最底层有几个元素最后一个输出的一定是是最底层最右的元素7那这里我们就想了能否将该处理与上一次题的翻转结合一下每一层都是先反转再放入队列就可以让最后一个输出的是最左的呢是的这就是解决本题的关键。 public int findBottomLeftValue(TreeNode root){if(root.right null root.left null){return root.val;}DequeTreeNode TreeQueue new ArrayDeque();TreeQueue.offer(root);TreeNode temp new TreeNode();while(!TreeQueue.isEmpty()){int len TreeQueue.size();for(int i 0; i len; i){temp TreeQueue.poll();//右节点先入队if(temp.right ! null){TreeQueue.offer(temp.right);}//左节点后入队if(temp.left ! null){TreeQueue.offer(temp.left);}}}return temp.val;}下面这个没有上面简洁而且相比之下增加了一些额外的开销仅供参考 public int findBottomLeftValue2(TreeNode root){if(root.right null root.left null){return root.val;}DequeTreeNode TreeQueue new ArrayDeque();TreeQueue.offer(root);int res 0;while(!TreeQueue.isEmpty()){int len TreeQueue.size();DequeTreeNode queue new ArrayDeque();for(int i 0; i len; i){TreeNode temp TreeQueue.poll();queue.addFirst(temp);if(temp.left ! null){TreeQueue.offer(temp.left);}if(temp.right ! null){TreeQueue.offer(temp.right);}}res queue.removeLast().val;}return res;}
