题目地址：二叉树的锯齿形层序遍历

思路

这道题与102题有很多相似之处，下面这篇文章是讲的107题，也有一定的参考意义。

那么对于这道题，我们的第一想法一定是需要一个布尔变量去判断是从左边开始还是从右边开始，

我们需要考虑一下如何让这个链表去呈现一个来回的效果

在官方题解中，使用一个双端队列来进行的一个解决

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;//边界的一点判断
        }
        Queue<TreeNode> queue = new LinkedList<>();//一个普通队列
        queue.add(root);//先添加根节点
        boolean isOrderLeft = true;//判断从左还是从右
        while (!queue.isEmpty()) {//while循环的条件为队列不为空
        
        }
     }

在while循环内，

我们依然是进行的那一套逻辑

{

1.当前队列有多长，就执行几个子操作

2.子操作是将当前节点的左右节点按照要求去塞到一个内部的小链表内

3.将小链表塞入最终的答案中

}

那么由于我们左右的顺序是需要调换的，我们是这么来进行，内部定义一个双端队列

        while (!queue.isEmpty()) {//while循环的条件为队列不为空
            Deque<Integer> levelList = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();


                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);//放到尾部，也就也是左->右
                } else {
                    levelList.offerFirst(curNode.val);//放到头部，也就也是右->左
                }


                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;

        }

如果需要从左往右去输出，就将当前节点放到队列尾部

就用这个链表去举一个例子

在while循环之前就将头节点1放入了queue队列，当前队列有1个，for循环操作进行一次

isOederLeft现在为true，也就是从左往右

那么就是将1放到队列levelList尾部，当然第一步只有一个节点看不出什么，

接下来就是将2和3依次放入queue队列，这里的依次是先左节点，后右节点，现在queue内部为【2 3】

然后就是将内部这个小队列变为链表塞入外部最终答案ans内，然后顺序调换，变为false

接着队列内有两个元素，for循环进行两次

弹出2

由于现在为false，所以将2放入levelList的头部，levelList为【2】

将2的左右节点放到queue内，现在queue内为【3 4 5】

进行第二次的循环

弹出3

由于现在为false，所以将3放入levelList的头部，levelList为【3 2】

这样也就实现了反向的操作

接下来是将3的左右也放进去queue现为【4 5 6 7】

完整代码

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
            return ans;//边界的一点判断
        }
        Queue<TreeNode> queue = new LinkedList<>();//一个普通队列
        queue.add(root);//先添加根节点
        boolean isOrderLeft = true;//判断从左还是从右
        while (!queue.isEmpty()) {//while循环的条件为队列不为空
            Deque<Integer> levelList = new LinkedList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();


                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);//如果从左边开始输出，那么就添加到队列的尾部
                } else {
                    levelList.offerFirst(curNode.val);//如果从右边开始输出，那么就添加到队列的头部
                }

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;

        }
        return ans;
    }