题目描述

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

例如：
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回锯齿形层次遍历如下：

1
2
3
4
5
\[
  \[3],
  \[20,9],
  \[15,7]
]

所谓的锯齿形遍历，即是在第一层从左向右遍历，在第二层从右向左遍历，依次遍历完成。

解题思路

我们将从根节点开始从0开始计数，那么就是在偶数层从左向右遍历，在奇数层从右向左遍历，如果我们能得到每一层的节点，那么在奇数层从后向前取，在偶数层从前向后取。

如果能做到从两端取值呢？我这里使用了双向链表LinkedList。

我们在遍历第n层时，要将这一次的数据放到结果集中，还要将下一次的节点按照先后顺序放到链表中。以上面的例子为例，在遍历第0层时，下一次的节点要按照(9,20)这样的顺序，在遍历第1层时，下一层的顺序要按照(15,7)这样的顺序。

这样就可以在每一层遍历开始前得到这一层的节点数量，然后对这一层的节点进行遍历。

我们如何保证在遍历节点时让下一层的节点按照我们想要的顺序呢？

看上面的例子，在第一层我们先获取20节点，这时先放了15,7这两个节点，如果9节点还有子节点那么我们要保证9节点的数据在20节点的数据之前。

除此之外，在每一层遍历时虽然得到了这一层节点的数量，但是我们并不是一次将他们全部取出，而这时子节点也需要放到链表中。我们要保证子节点不能与当前层的数据混合。

我使用了一个更加复杂一些的例子花了一个流程图，看完这个应该能更好理解：

代码实现：

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
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  if (root == null) {
    return Collections.emptyList();
  }
  List<List<Integer>> result = new ArrayList<>();
  LinkedList<TreeNode> queue = new LinkedList<>();
  queue.addFirst(root);
  int level = 0;
  while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> con = new LinkedList<>();
    if (level % 2 == 0) {
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.pollFirst();
        con.add(node.val);
        if (node.left != null) {
          queue.addLast(node.left);
        }
        if (node.right != null) {
          queue.addLast(node.right);
        }
      }
    } else {
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.pollLast();
        con.add(node.val);
        if(node.right!=null){
          queue.addFirst(node.right);
        }
        if(node.left!=null){
          queue.addFirst(node.left);
        }
      }
    }
    result.add(con);
    level++;
  }
  return result;
}

这里是先从左到右，然后从右到左的顺序。如果题目要求先从右到左，在从左到右的顺序。可以在代码中将pollLast与pollFirst进行交换即可。