题目连接

示例

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],

3<br />   / \<br />  9  20<br />    /  \<br />   15   7<br />返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

解题思路

沿用第 102 题leectode102-二叉树的层序遍历的思想，修改广度优先搜索，对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度 size，每次从队列中取出 size 个元素进行拓展，然后进行下一次迭代。

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

原先逐层遍历的思路不变，维护一个变量 isOrderLeft记录是从左至右还是从右至左的。

• 如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
• 如果从右至左，我们每次将被遍历到的元素插入至双端队列的头部。

当遍历结束的时候我们就得到了答案数组。

代码

// 二叉树的锯齿形层序遍历
public class leetcode103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) return lists;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isOrderLeft = true;
        while (queue.size() > 0){
            Deque<Integer> deque = new LinkedList<>();
            int size = queue.size();
            for (int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if (isOrderLeft){
                    deque.offerLast(node.val);
                }else {
                    deque.offerFirst(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            lists.add(new LinkedList<Integer>(deque));
            isOrderLeft = !isOrderLeft;
        }
        return lists;
    }
}