Leetcode103. 二叉树的锯齿形层序遍历

题目描述

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

思路分析

1. 对二叉树锯齿形层序遍历，实质为对二叉树层序遍历的扩展
2. 使用一个单向队列记录每一层的节点，然后对其进行遍历
3. 使用一个双向队列记录每一层的节点值，因为是锯齿形遍历，可以使用一个标志位，使得当前层如果正向遍历，则下一层对标志位取反，使其反向遍历，然后记录节点值
4. 详细分析见下

源码及分析

/**
     *
     * @param root 根节点
     * @return 返回遍历的结果集
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        //定义集合保存遍历的结果集
        ArrayList<List<Integer>> res = new ArrayList<>();
        //根节点校验
        if (root == null) {
            return res;
        }
        //创建单向队列保存每一层的节点
        Queue<TreeNode> queueNode = new LinkedList<>();
        //根节点先入队列
        queueNode.offer(root);
        //定义标志位，即如果当前行从左到右遍历，则下一行从右往左遍历
        Boolean isOrderLeft = true;
        //循环遍历每一层，直到所有层都遍历结束
        while (!queueNode.isEmpty()) {
            //定义双向队列，因为每次入队列和出队列的方向不一致
            Deque<Integer> levelVal = new LinkedList<>();
            //记录当前层节点的个数，然后对其进行遍历
            int size = queueNode.size();
            for (int i = 0; i < size; i++) {
                //从当前层中取出一个节点
                TreeNode curNode = queueNode.poll();
                //判断是从左到右还是从右往左，然后将节点值添加到队列中不同设定位置
                if (isOrderLeft) {
                    levelVal.offerLast(curNode.val);
                } else {
                    levelVal.offerFirst(curNode.val);
                }
                //如果当前节点的左右子节点不为空，则入队列进行下一次遍历
                if (curNode.left != null) {
                    queueNode.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queueNode.offer(curNode.right);
                }
            }
            //保存结果
            res.add(new ArrayList<>(levelVal));
            //标志位取反，实现锯齿遍历
            isOrderLeft = !isOrderLeft;
        }
        return res;
    }