剑指offer第六十题。

题目描述

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

解题思路

一开始我以为就是简单的层序遍历嘛:

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
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<>();

if(pRoot == null){
return res;
}

LinkedList<TreeNode> queue = new LinkedList<>();

queue.add(pRoot);

while(!queue.isEmpty()){
TreeNode node = queue.pop();
ArrayList<Integer> list = new ArrayList<>();
list.add(node.val);

if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}

if(list.size() != 0){
res.add(list);
}
}

return res;
}

}

然后结果是:

1
2
3
4
5
6
7
8
9
10
用例:
{8,6,10,5,7,9,11}

对应输出应该为:

[[8],[6,10],[5,7,9,11]]

你的输出为:

[[8],[6],[10],[5],[7],[9],[11]]

事实上,这里需要将在同一层的数放到一个集合之中,所以还需要加工一下才行。

我的答案

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
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > res = new ArrayList<>();

if(pRoot == null){
return res;
}

LinkedList<TreeNode> queue = new LinkedList<>();

queue.add(pRoot);

//先把root放进结果集
ArrayList<Integer> list = new ArrayList<>();
list.add(pRoot.val);
res.add(list);

while(!queue.isEmpty()){
//统计一下当前队列中的个数,因为当前队列中存放的都是同一层的数据
//所以需要对这一层进行处理
int num = queue.size();
list = new ArrayList<>();
while(num > 0){
TreeNode node = queue.pop();
if(node.left != null){
list.add(node.left.val);
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
list.add(node.right.val);
}
num--;
}
if(list.size() != 0){
res.add(list);
}
}
return res;
}

}