Binary Tree ZigZag Level Order Traversal leetcode java
4093 ワード
タイトル:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree
return its zigzag level order traversal as:
public ArrayList> zigzagLevelOrder(TreeNode root) {
2 ArrayList> res =
new ArrayList>();
3
4
if(root==
null)
5
return res;
6
7 LinkedList queue =
new LinkedList();
8 queue.add(root);
9
10
int num = 0;
11
boolean reverse =
false;
//
a flag
12
13
while(!queue.isEmpty()){
14 num = queue.size();
15 ArrayList levelres =
new ArrayList();
16
17
for(
int i = 0; i18 TreeNode node = queue.poll();
19 levelres.add(node.val);
20
21
if(node.left!=
null)
22 queue.add(node.left);
23
if(node.right!=
null)
24 queue.add(node.right);
25 }
26
27
if(reverse){
28 Collections.reverse(levelres);
29 reverse =
false;
30 }
else{
31 reverse =
true;
32 }
33 res.add(levelres);
34 }
35
36
return res;
37 }
public ArrayList> zigzagLevelOrder(TreeNode root) {
2 ArrayList> res =
new ArrayList>();
3
if(root ==
null)
4
return res;
5
6 LinkedList queue =
new LinkedList();
7 queue.add(root);
8 Boolean reverse =
false;
9
int nextlevel = 0;
10
int currlevel = 1;
11 ArrayList tmp =
new ArrayList();
12
while(!queue.isEmpty()){
13 TreeNode t = queue.poll();
14 tmp.add(t.val);
15 currlevel--;
16
17
if(t.left!=
null){
18 queue.add(t.left);
19 nextlevel++;
20 }
21
22
if(t.right!=
null){
23 queue.add(t.right);
24 nextlevel++;
25 }
26
27
if(currlevel == 0){
28 currlevel = nextlevel;
29 nextlevel = 0;
30
if(reverse){
31 Collections.reverse(tmp);
32 reverse =
false;
33 }
else{
34 reverse =
true;
35 }
36 res.add(tmp);
37 tmp =
new ArrayList();
38 }
39 }
40
41
return res;
42 }
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree
{3,9,20,#,#,15,7}
, 3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
:
BFS, flag reverse, reverse 。
:
1 public ArrayList
2 ArrayList
new ArrayList
3
4
if(root==
null)
5
return res;
6
7 LinkedList
new LinkedList
8 queue.add(root);
9
10
int num = 0;
11
boolean reverse =
false;
//
a flag
12
13
while(!queue.isEmpty()){
14 num = queue.size();
15 ArrayList
new ArrayList
16
17
for(
int i = 0; i
19 levelres.add(node.val);
20
21
if(node.left!=
null)
22 queue.add(node.left);
23
if(node.right!=
null)
24 queue.add(node.right);
25 }
26
27
if(reverse){
28 Collections.reverse(levelres);
29 reverse =
false;
30 }
else{
31 reverse =
true;
32 }
33 res.add(levelres);
34 }
35
36
return res;
37 }
1 public ArrayList
2 ArrayList
new ArrayList
3
if(root ==
null)
4
return res;
5
6 LinkedList
new LinkedList
7 queue.add(root);
8 Boolean reverse =
false;
9
int nextlevel = 0;
10
int currlevel = 1;
11 ArrayList
new ArrayList
12
while(!queue.isEmpty()){
13 TreeNode t = queue.poll();
14 tmp.add(t.val);
15 currlevel--;
16
17
if(t.left!=
null){
18 queue.add(t.left);
19 nextlevel++;
20 }
21
22
if(t.right!=
null){
23 queue.add(t.right);
24 nextlevel++;
25 }
26
27
if(currlevel == 0){
28 currlevel = nextlevel;
29 nextlevel = 0;
30
if(reverse){
31 Collections.reverse(tmp);
32 reverse =
false;
33 }
else{
34 reverse =
true;
35 }
36 res.add(tmp);
37 tmp =
new ArrayList
38 }
39 }
40
41
return res;
42 }