1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> levels = new LinkedList<>();
dfs(root, 0, levels);
return levels;
}
private void dfs(TreeNode node, int level, LinkedList<List<Integer>> levels) {
if (node == null) {
return;
}
if (levels.size() == level) {
levels.addFirst(new ArrayList<>());
}
levels.get(levels.size() - 1 - level).add(node.val);
dfs(node.left, level + 1, levels);
dfs(node.right, level + 1, levels);
}
}
|
就是把新的level加到开头即可. 那如何获得某个level在list中的位置呢? 我们发现规律:
level 0在末尾, level 1在倒数第二… 因此level + 它的index = list.size() - 1. 于是当我们遇到一个level, 它在list中的index就是list.size() - 1 - level.
时间复杂度: O(n)
空间复杂度: O(n)
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
| class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> levels = new LinkedList<>();
if (root == null) {
return levels;
}
Deque<TreeNode> nodeQ = new ArrayDeque<>();
nodeQ.offer(root);
while (!nodeQ.isEmpty()) {
List<Integer> currLevel = new ArrayList<>();
for (int i = nodeQ.size(); i > 0; i--) {
TreeNode currNode = nodeQ.poll();
currLevel.add(currNode.val);
if (currNode.left != null) {
nodeQ.offer(currNode.left);
}
if (currNode.right != null) {
nodeQ.offer(currNode.right);
}
}
levels.addFirst(currLevel);
}
return levels;
}
}
|
BFS的写法. 时间复杂度和空间复杂度不变.
