LeetCode 103. 二叉树的锯齿形层序遍历 题解，理解经典层序遍历。

题目

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

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

借助队列层序遍历

思路

本题是层序遍历的小变体，借助队列，我们暂存遍历到的二叉树节点：

  • 逐层消费队列中的节点，其中队列进入一轮循环中获得当前层的节点数（size）；
  • 奇偶层我们使用一个变量标识，随层反转；

复杂度分析

时间

遍历一次树即可，时间复杂度O(n)。

空间

额外空间我们借助了一个Queue来构建层数据，空间复杂度O(n)。ansList不属于额外空间。

代码

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/**
* 执行用时：
* 1 ms
* , 在所有 Java 提交中击败了
* 72.18%
* 的用户
* 内存消耗：
* 40 MB
* , 在所有 Java 提交中击败了
* 74.53%
* 的用户
* 通过测试用例：
* 33 / 33
*/
@SuppressWarnings("unchecked")
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
        return new ArrayList<>(0);
    }
    List<List<Integer>> ans = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    // 奇数层从左向右，偶数层相反
    boolean oddLevel = true;
    while (!queue.isEmpty()) {

        Deque<Integer> innerList = new LinkedList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode curr = queue.poll();

            if (curr == null) {
                continue;
            }

            queue.offer(curr.left);
            queue.offer(curr.right);

            if (oddLevel) {
                innerList.offerLast(curr.val);
            } else {
                innerList.offerFirst(curr.val);
            }
        }
        if (!innerList.isEmpty()) {
            ans.add((List<Integer>) innerList);
        }
        oddLevel = !oddLevel;
    }
    return ans;
}