难度中等525
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [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]
]
|
通过次数173,983
提交次数304,411
这一题的坑还是非常多的，没有那么容易。最初想法是改一改层序遍历的代码就行了，想用一个队列完成，根据flag决定出队列的顺序。发现不行，因为队列是一遍增加一遍移出的。入上图当队列是[9 20]，从尾部移出得到20，9.看起来没错，但是在移出9时，又像队列的尾部增加了15和7，队列变成了[9 15 7]再移出尾部就错了。
这是想通过双队列的方式，增加到新的队列中，在移出9时，[15 7]在下一个队列。看起来比较完美，一试又不对。试想移出9时插入[15 7] 再移出20时，插入了20的子节点（这里假设它有2个子节点 1 2），会发现倒序的里面，是左节点，右节点的顺序，很奇怪。此时又想过根据flag实现从右到左，但是这似乎让顺序直接变成倒叙的队列，下一行就不必改变出队列的顺序，一直倒序出就可以了。
但是这种太麻烦，我最后还是用了顺序的bfs，但是根据flag的值，让输出的值取反，实现不对bfs的过程做出任何改变，较为简易。
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
53
54
55
56
57
58
59
60
61
62
63
|
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<List<Integer>> ans=new ArrayList<>();
if(root==null) return ans;
LinkedList<TreeNode> queue=new LinkedList<>();
LinkedList<TreeNode> queueNext=new LinkedList<>();
LinkedList<TreeNode> queueCopy=new LinkedList<>();
ArrayList<Integer> zigzag=new ArrayList<>();
queue.add(root);
queueCopy.add(root);
int flag=1;
int cur=1;
int next=0;
zigzag=new ArrayList<>();
while(!queue.isEmpty()&&!queueCopy.isEmpty()){
TreeNode t=null;
TreeNode tcopy=null;
if(flag==1){t=queue.removeFirst();}
else if(flag==-1){t=queue.removeLast();}
tcopy=queueCopy.poll();
zigzag.add(t.val);
cur--;
if(tcopy.left!=null){
queueNext.add(tcopy.left);
next++;
}
if(tcopy.right!=null){
queueNext.add(tcopy.right);
next++;
}
if(cur==0){
ans.add(zigzag);
// System.out.println(queueNext);
zigzag=new ArrayList<>();
flag=-flag;
queue=new LinkedList(queueNext);
queueCopy=new LinkedList(queueNext);
// 注意不能传地址：queue=queueNext 这样会使queue 和queueNext指向的是同一个地址
queueNext.clear();
cur=next;
next=0;
}
}
return ans;
}
}
|