二叉树的锯齿形层序遍历[中等]

优质博文：IT-BLOG-CN

一、题目

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

树中节点数目在范围[0, 2000]内
-100 <= Node.val <= 100

二、代码

广度优先遍历： 规定二叉树的根节点为第0层，如果当前层数是偶数，从左至右输出当前层的节点值，否则，从右至左输出当前层的节点值。我们依然可以沿用第102题的思想，修改广度优先搜索，对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 size，每次从队列中取出size个元素进行拓展，然后进行下一次迭代。

为了满足题目要求的返回值为「先从左往右，再从右往左」交替输出的锯齿形，我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。

双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个变量isOrderLeft记录是从左至右还是从右至左的：
【1】如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
【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 ArrayDeque<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;}}

时间复杂度： 其中N为二叉树的节点数。每个节点会且仅会被遍历一次。
空间复杂度： O(N)。我们需要维护存储节点的队列和存储节点值的双端队列，空间复杂度为O(N)。