二叉树的锯齿形遍历，力扣

目录

题目：

我们直接看题解吧：

快速理解解题思路小建议：

解题方法：

相似题目对比分析：

解题分析：

解题思路：

补充说明：

思路优化：

代码实现(层序遍历+倒序)：

---

题目地址：

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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();//创建双端队列，存放每层树的节点List<List<Integer>> res = new ArrayList<>();//创建二维列表，存储遍历所得节点值if (root != null) queue.add(root);  //若根节点非空，则将根节点添加至queue队列while (!queue.isEmpty()) {//BFS循环，当deque为空时跳出循环LinkedList<Integer> 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()) {// 打印奇数层List<Integer> 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if (root != null) queue.add(root);while (!queue.isEmpty()) {List<Integer> 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;}
}