Binary Tree Level Order Traversal leetcode java
2066 ワード
タイトル:
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree
return its level order traversal as:
public ArrayList> levelOrder(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
int curLevCnt = 1;
9
int nextLevCnt = 0;
10 ArrayList levelres =
new ArrayList();
11
12
while(!queue.isEmpty()){
13 TreeNode cur = queue.poll();
14 curLevCnt--;
15 levelres.add(cur.val);
16
17
if(cur.left !=
null){
18 queue.add(cur.left);
19 nextLevCnt++;
20 }
21
if(cur.right !=
null){
22 queue.add(cur.right);
23 nextLevCnt++;
24 }
25
26
if(curLevCnt == 0){
27 curLevCnt = nextLevCnt;
28 nextLevCnt = 0;
29 res.add(levelres);
30 levelres =
new ArrayList();
31 }
32 }
33
return res;
34 }
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree
{3,9,20,#,#,15,7}
, 3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
:
BFS 。 :
1 public ArrayList
2 ArrayList
new ArrayList
3
if(root ==
null)
4
return res;
5
6 LinkedList
new LinkedList
7 queue.add(root);
8
int curLevCnt = 1;
9
int nextLevCnt = 0;
10 ArrayList
new ArrayList
11
12
while(!queue.isEmpty()){
13 TreeNode cur = queue.poll();
14 curLevCnt--;
15 levelres.add(cur.val);
16
17
if(cur.left !=
null){
18 queue.add(cur.left);
19 nextLevCnt++;
20 }
21
if(cur.right !=
null){
22 queue.add(cur.right);
23 nextLevCnt++;
24 }
25
26
if(curLevCnt == 0){
27 curLevCnt = nextLevCnt;
28 nextLevCnt = 0;
29 res.add(levelres);
30 levelres =
new ArrayList
31 }
32 }
33
return res;
34 }