算法题400：二叉树的锯齿形层次遍历
The following article is from 数据结构和算法 Author 山大王wld
（给算法爱好者加星标，修炼编程内功）
来源： 数据结构和算法-山大王wld
问题描述
今天来看一道比较简单的题，给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
BFS打印
二叉树的的层次遍历就是一层一层的遍历，也就是我们俗称的BFS（宽度优先搜索算法（又称广度优先搜索））,树的宽度优先搜索，最简单的方式就是使用队列。但这题打印的时候多了一个条件，就是不能一直从一个方向打印，要先从左边打印然后再从右边打印……，就这样交替进行，所以这里要有个变量来判断是从左往右还是从右往左打印，代码比较简单，我们来看下。
1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2 List<List<Integer>> res = new ArrayList<>();
3 if (root == null)
4 return res;
5 Queue<TreeNode> queue = new LinkedList<>();
6 queue.add(root);
7 boolean leftToRight = true;
8 while (!queue.isEmpty()) {
9 List<Integer> level = new ArrayList<>();
10 //统计这一行有多少个节点
11 int count = queue.size();
12 //遍历这一行的所有节点
13 for (int i = 0; i < count; i++) {
14 //poll移除队列头部元素（队列在头部移除，尾部添加）
15 TreeNode node = queue.poll();
16 //判断是从左往右打印还是从右往左打印。
17 if (leftToRight) {
18 level.add(node.val);
19 } else {
20 level.add(0, node.val);
21 }
22 //左右子节点如果不为空会被加入到队列中
23 if (node.left != null)
24 queue.add(node.left);
25 if (node.right != null)
26 queue.add(node.right);
27 }
28 res.add(level);
29 leftToRight = !leftToRight;
30 }
31 return res;
32}
上面代码中如果把第17-21行的代码直接换成第18行的代码就是我们之前讲过的BFS，就是一层一层往下打印。只不过这里多了一个条件的判断。
当然我们还可以根据每一层是第几层来判断，如果根节点是第1层的话，那么我们在层数是奇数的时候从左往右打印，如果层数是偶数的时候从右往左打印。这里我们使用上面两种方式的结合，来看下代码。
1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2 List<List<Integer>> res = new ArrayList<>();
3 if (root == null)
4 return res;
5 //双端队列，两边都可以操作
6 Deque<TreeNode> deque = new LinkedList<>();
7 //添加到队列的头
8 deque.addFirst(root);
9 while (!deque.isEmpty()) {
10 List<Integer> level = new ArrayList<>();
11 //统计这一行有多少个节点
12 int count = deque.size();
13 //遍历这一行的所有节点
14 TreeNode cur;
15 for (int i = 0; i < count; i++) {
16 if (res.size() % 2 == 1) {
17 //从左边往右边打印
18 //移除队列头部的元素，如果子节点不为空加入到队列的尾部
19 cur = deque.removeFirst();
20 if (cur.right != null)
21 deque.addLast(cur.right);
22 if (cur.left != null)
23 deque.addLast(cur.left);
24 } else {
25 //从右边往左边打印
26 //移除队列尾部的元素，如果子节点不为空加入到队列的头部
27 cur = deque.removeLast();
28 if (cur.left != null)
29 deque.addFirst(cur.left);
30 if (cur.right != null)
31 deque.addFirst(cur.right);
32 }
33 level.add(cur.val);
34 }
35 res.add(level);
36 }
37 return res;
38}
DFS打印
这题除了使用BFS以外，我们还可以使用DFS。但这里我们要有个判断，如果走到下一层的时候集合没有创建，我们要先创建下一层的集合，代码也很简单，我们来看下。
1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2 List<List<Integer>> res = new ArrayList<>();
3 travel(root, res, 0);
4 return res;
5}
6
7private void travel(TreeNode cur, List<List<Integer>> res, int level) {
8 if (cur == null)
9 return;
10 //如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
11 if (res.size() <= level) {
12 List<Integer> newLevel = new LinkedList<>();
13 res.add(newLevel);
14 }
15 //遍历到第几层我们就操作第几层的数据
16 List<Integer> list = res.get(level);
17 //这里默认根节点是第0层，偶数层相当于从左往右遍历，
18 // 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
19 // 要把数据添加到集合的开头
20 if (level % 2 == 0)
21 list.add(cur.val);
22 else
23 list.add(0, cur.val);
24 //分别遍历左右两个子节点，到下一层了，所以层数要加1
25 travel(cur.left, res, level + 1);
26 travel(cur.right, res, level + 1);
27}
总结
这题最简单的一种方式就是参照二叉树的BFS打印，然后稍作修改，如果当前行是从左往右打印，那么下一行就从右往左打印。如果当前行是从右往左打印，那么下一行就从左往右打印，代码基本上没什么难度。
- EOF -
觉得本文有帮助？请分享给更多人
关注「算法爱好者」加星标，修炼编程内功
好文章，我在看❤️