描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{1,2,3,#,#,4,5}

示例1

输入：
{1,2,3,#,#,4,5}

返回值：
[[1],[3,2],[4,5]]

示例2

输入：
{8,6,10,5,7,9,11}

返回值：
[[8],[10,6],[5,7,9,11]]

示例3

输入：
{1,2,3,4,5}

返回值：
[[1],[3,2],[4,5]]

思路

按层遍历二叉树，不知道大家了不了解，按层便利就是将每层的元素，按照从左到右的顺序输出。而这道题要求的 之 字形便利，则是第一层是从左到右，下一层则是从右到左。如果之前会写按层遍历，在写这道题会相对简单一点。

以上面这棵树为例：

1. 首先咱们通过 队列 这个数据结构来实现每层元素的存储，当遍历到第一层的时候，这时是从左到右的顺序入队列，入了队列之后值存入到集合中。然后再将左节点以及右节点入队。
2. 这时到了第二层，这层的顺序是从右到左了，从队列中出队，弹出元素，将上一层所有的元素都弹出后，以相反的顺序存入到集合中。
3. 之后重复上面的动作，知道完成便利。

AC代码

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) {
            return result;
        }
        // 创建一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点先入队
        queue.offer(pRoot);
        // 当队列不为空时
        while (!queue.isEmpty()) {

            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<>();
            // 仅遍历当前层的元素，因为结果是按照层的维度存储的
            for (int i = 0; i < size; i ++) {
                // 弹出元素
                TreeNode node = queue.poll();
                list.add(node.val);
                // 如果左节点不为空，则入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                // 如果右节点不为空，则入队
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 判断一下是否为奇数层，如果是，则将结果反着存储，
            // 这里将根节点那层设定为 第 0 层，为偶数层
            if (result.size() % 2 == 1) {
                Collections.reverse(list);
            }
            // 将结果以 层 为维度存储
            result.add(list);
        }
        return result;
    }

时间复杂度：O(N), N 为节点数，每个节点都要遍历一次
空间复杂度：o(N), N 为节点数，将这些节点存入到队列中

最后

做这道题之前最后先做一下 层序遍历二叉树，这道题只不过是变了一下而已。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。