Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
return its bottom-up level order traversal as:
1
2
3
4
5
|
[
[15,7],
[9,20],
[3]
]
|
解法
遍历方法依然是从上往下遍历，但是存的时候需要对列表做一次翻转。
具体代码如下：
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
|
class {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null)
return res;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> tmplist = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode tmp = q.poll();
if (tmp.left != null) {
q.offer(tmp.left);
}
if (tmp.right != null) {
q.offer(tmp.right);
}
tmplist.add(tmp.val);
}
res.add(tmplist);
}
List<List<Integer>> finalres = new ArrayList<>();
for (int i = res.size() - 1; i >= 0; i--) {
finalres.add(res.get(i));
}
return finalres;
}
}
|
近期评论