人才网站,淘宝网页版手机版,建设注册证信息网站,天坛整装体验馆地址目录 题目#xff1a; 我们直接看题解吧#xff1a; 快速理解解题思路小建议#xff1a; 解题方法#xff1a; 相似题目对比分析#xff1a; 解题分析#xff1a; 解题思路#xff1a; 补充说明#xff1a; 思路优化#xff1a; 代码实现(层序遍历倒序)#xff1a; 题…目录 题目 我们直接看题解吧 快速理解解题思路小建议 解题方法 相似题目对比分析 解题分析 解题思路 补充说明 思路优化 代码实现(层序遍历倒序) 题目地址 103. 二叉树的锯齿形层序遍历 - 力扣LeetCode 难度中等 今天刷二叉树的锯齿形遍历大家有兴趣可以点上面链接看看题目要求试着做一下。 题目
二叉树的锯齿形遍历给你二叉树的根节点 root 返回其节点值的 锯齿形层序遍历 。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。 我们直接看题解吧
快速理解解题思路小建议 可以先简单看一下解题思路然后照着代码看思路会更容易理解一些。 审题目事例提示 注意输出结果为二维列表 解题方法 方法1层序遍历双端队列(广度优先搜索) 方法2层序遍历倒序 相似题目对比分析 相似题目解题链接- 二叉树的层序遍历力扣-CSDN博客 此题是「102 二叉树的层序遍历」的变种最后输出的要求有所变化要求我们按层数的奇偶来决定每一层的输出顺序即结果打印顺序需要交替变化。 解题分析 规定二叉树的根节点为第 0 层 如果当前层数是偶数从左至右输出当前层的节点值 否则从右至左输出当前层的节点值。 因此可以沿用第 102 题的思想修改广度优先搜索对树进行逐层遍历用队列维护当前层的所有元素当队列不为空的时候求得当前队列的长度 size每次从队列中取出 size 个元素进行拓展然后进行下一次迭代。 为了满足题目要求的返回值为「先从左往右再从右往左」交替输出的锯齿形我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。双端队列是一个可以在队列任意一端插入元素的队列。 解题思路 利用双端队列的两端可添加元素的特性设打印列表(双端对列)tmp,规定 奇数层则添加值tmp尾部 偶数层则添加值tmp头部。 另外 方法1解题代码简短、容易实现但需要判断每个节点的所在层奇偶性即冗余了 N次判断。 具体流程 1、创建队列queue与列表res 2、BFS循环当deque为空时跳出循环 a.创建新列表tmp用于临时存储当前层的遍历结果 b.当前层的遍历循环循环次数为当前层的节点数(即deque长度) ·出队队首元素出队赋值节点node ·打印若为奇数层将node.val添加至tmp尾部反之 ·添加子节点若node的左()右节点非空则加入deque c.将当前层结果tmp转为list并加入res. 3、返回打印结果列表res. 可结合理解-103. 二叉树的锯齿形层序遍历 - 力扣LeetCode 代码实现
/*** 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) {QueueTreeNode queue new LinkedList();//创建双端队列存放每层树的节点ListListInteger res new ArrayList();//创建二维列表存储遍历所得节点值if (root ! null) queue.add(root); //若根节点非空则将根节点添加至queue队列while (!queue.isEmpty()) {//BFS循环当deque为空时跳出循环LinkedListInteger tmp new LinkedList();//创建新列表tmp用于临时存储当前层的遍历结果for(int i queue.size(); i 0; i--) {//循环次数为当前层的节点数(即deque长度)TreeNode node queue.poll();//队首元素出队赋值节点nodeif (res.size() % 2 0) tmp.addLast(node.val);//若为奇数层将node.val添加至tmp尾部反之else tmp.addFirst(node.val);if (node.left ! null) queue.add(node.left);//若node的左节点非空则加入dequeif (node.right ! null) queue.add(node.right);//若node的右节点非空则加入deque}res.add(tmp);//将当前层遍历结果添加到res}return res;}
}
补充说明 1、特殊处理当树的根节点为空则直接返回空列表[] 2、 打印结果空列表 res 包含根节点的双端队列 deque相当于初始化操作 。 3、本题解题代码将链表 LinkedList 作为双端队列使用 4、注意这个是伪锯齿形遍历相当于只是结果字符串反转了而已遍历都是从左往右遍历只不过在组装结果的时候改变了顺序而没有按照先从左往右再从右往左进行下一层遍历。 思路优化 由方法1解题可知该方法需要判断每个节点的所在层奇偶性即冗余了 N次判断 因此通过将奇偶层逻辑拆分可以消除冗余的判断进一步优化解题方法。 主要优化在 BFS 循环部分。 算法流程 BFS 循环 循环打印奇 / 偶数层当 deque 为空时跳出。 打印奇数层 从左向右打印先左后右 加入下层节点。 若 deque 为空说明向下无偶数层则跳出。 打印偶数层 从右向左 打印先右后左 加入下层节点。 while (!deque.isEmpty()) {// 打印奇数层ListInteger tmp new ArrayList();for(int i deque.size(); i 0; i--) {// 从左向右打印TreeNode node deque.removeFirst();tmp.add(node.val);// 先左后右加入下层节点if (node.left ! null) deque.addLast(node.left);if (node.right ! null) deque.addLast(node.right);}res.add(tmp);if (deque.isEmpty()) break; // 若为空则提前跳出// 打印偶数层tmp new ArrayList();for(int i deque.size(); i 0; i--) {// 从右向左打印TreeNode node deque.removeLast();tmp.add(node.val);// 先右后左加入下层节点if (node.right ! null) deque.addFirst(node.right);if (node.left ! null) deque.addFirst(node.left);}res.add(tmp);}代码实现(层序遍历倒序) 此方法的优点是只用列表即可无需其他数据结构。偶数层倒序 若 res 的长度为 奇数 说明当前是偶数层则对 tmp 执行 倒序 操作。 class Solution {public ListListInteger zigzagLevelOrder(TreeNode root) {QueueTreeNode queue new LinkedList();ListListInteger res new ArrayList();if (root ! null) queue.add(root);while (!queue.isEmpty()) {ListInteger tmp new ArrayList();for(int i queue.size(); i 0; i--) {TreeNode node queue.poll();tmp.add(node.val);//直接添加节点if (node.left ! null) queue.add(node.left);//添加子节点if (node.right ! null) queue.add(node.right);}//偶数层倒序若res的长度为奇数说明当前是偶数层则对tmp执行倒序操作。if (res.size() % 2 1) Collections.reverse(tmp);res.add(tmp);}return res;}
}
