二叉树的锯齿形层序遍历

在这里插入图片描述

代码逻辑

这道题如果用队列（Queue）来做层序遍历，然后每层根据奇偶性决定是正序还是反序。

这样操作会遇到一些麻烦，比如用双端队列（Deque），需要频繁在两端操作；如果用普通队列，收集结果时需要反转列表。

今天分享一种解法：

用一个静态数组模拟队列，通过索引控制实现锯齿形遍历。

1. 用数组模拟队列

1
2


public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;  // l是队头，r是队尾

2. 双循环结构

第一个循环：收集当前层的节点值

1
2
3
4
5
6


for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; 
     k < size; 
     i += j, k++) {
    TreeNode cur = queue[i];
    list.add(cur.val);
}

如果 reverse == false（从左到右）：i 从 l 开始，每次 +1；

如果 reverse == true（从右到左）：i 从 r-1 开始，每次 -1；

第二个循环：扩展下一层节点

1
2
3
4
5
6
7
8
9


for (int i = 0; i < size; i++) {
    TreeNode cur = queue[l++];  // 从队头取出
    if (cur.left != null) {
        queue[r++] = cur.left;   // 放入队尾
    }
    if (cur.right != null) {
        queue[r++] = cur.right;
    }
}

按照左到右的顺序处理节点，把下一层的节点依次加入队列。

完整代码

 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


public static int MAXN = 2001;
	public static TreeNode[] queue = new TreeNode[MAXN];
	public static int l, r;  // l是队头，r是队尾

	public static List<List<Integer>> zigzagLevelOrder(TreeNode root){
		List<List<Integer>> ans = new ArrayList<>();
		if(root!=null){
			l=r=0;
			queue[r++]=root;
			boolean reverse = false;
			while(l<r){
				int size = r-l;
				ArrayList<Integer> list = new ArrayList<>();
				for(int i=reverse?r-1:l,j=reverse?-1:1,k=0;k<size;i+=j,k++){
					TreeNode cur = queue[i];
					list.add(cur.val);
				}
				for (int i = 0; i < size; i++) {
					TreeNode cur = queue[l++];  // 从队头取出
					if (cur.left != null) {
						queue[r++] = cur.left;   // 放入队尾
					}
					if (cur.right != null) {
						queue[r++] = cur.right;
					}
				}
				ans.add(list);
				reverse = !reverse;
			}
		}
		return ans;
	}