一、题目
1、算法题目
“给定二叉树的根节点，返回其节点值的锯齿形层序遍历。”
题目链接：
来源：力扣（LeetCode）
链接：103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
网络异常，图片无法展示
|
示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [[3],[20,9],[15,7]] 复制代码
示例 2： 输入： root = [1] 输出： [[1]] 复制代码
二、解题
1、思路分析
我发现最近几天的题目都是二叉树，是让我们彻底搞懂二叉树嘛。。。
OK，言归正传，这道题是102题二叉树的层序遍历的变化而来，只是对最后的输出有所变化，要求我们按照锯尺层序遍历。也就是从左往右遍历树节点，然后再从右向左遍历树节点。
这道题依旧可以使用102题的思路，使用广度优先搜索算法，对树进行逐层遍历，用队列去维护当前层所有元素，当队列不为空的时候，求得队列长度，每次从队列汇总取出队列长度的元素进行下一次迭代。
为了解题，我们可以使用双端队列的数据结构来维护当前层节点值输出的顺序，双端队列是一个可以在队列任意一端插入元素的队列。
那么就可以这样：
- 如果从左向右遍历，将遍历的元素插入双端队列的尾部
- 如果从右向左遍历，将遍历的元素插入双端队列的首部
遍历结束，就得到了我们想要的数组答案了。
2、代码实现
代码参考：
class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> ans = new LinkedList<List<Integer>>(); if (root == null) { return ans; } Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>(); nodeQueue.offer(root); boolean isOrderLeft = true; while (!nodeQueue.isEmpty()) { Deque<Integer> levelList = new LinkedList<Integer>(); int size = nodeQueue.size(); for (int i = 0; i < size; ++i) { TreeNode curNode = nodeQueue.poll(); if (isOrderLeft) { levelList.offerLast(curNode.val); } else { levelList.offerFirst(curNode.val); } if (curNode.left != null) { nodeQueue.offer(curNode.left); } if (curNode.right != null) { nodeQueue.offer(curNode.right); } } ans.add(new LinkedList<Integer>(levelList)); isOrderLeft = !isOrderLeft; } return ans; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(N)
其中N是二叉树的节点数，每个节点数都会被遍历一次。
空间复杂度： O(N)
需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为O(N)。
三、总结
在广度优先搜索算法的基础上，区分每一层，就得到了层序遍历。
然后使用双端队列储存每个节点的值，遍历完成后，就得到了我们想要的答案了。
