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

题目描述

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

输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
       3
      / \
     9  20
        / \
       15  7

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

输入：root = [1]
输出：[[1]]

输入：root = []
输出：[]

基本思路

在层次遍历的基础上添加一个boolean isOrderLeft 判断是否要从Deque双端队列的前边或者后边插入

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null) return res;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        boolean isOrderLeft = true;

        while(!queue.isEmpty()) {
            Deque<Integer> value = new LinkedList<Integer>();
            int currentLevel = queue.size();
            for(int i = 0; i < currentLevel; i++){
                TreeNode node = queue.poll();// 出队尾元素 先进先出
                if(isOrderLeft){
                    value.offerLast(node.val);
                }else{
                    value.offerFirst(node.val);
                }
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            res.add(new LinkedList<Integer>(value));
            isOrderLeft = !isOrderLeft;
        }
        return res;
    }
}