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 Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Map<Integer, List<Integer>> colNodesMap = new HashMap<>();
Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
q.offer(new Pair<>(root, 0));
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
while (!q.isEmpty()) {
Pair<TreeNode, Integer> currPair = q.poll();
colNodesMap.putIfAbsent(currPair.getValue(), new ArrayList<>());
colNodesMap.get(currPair.getValue()).add(currPair.getKey().val);
if (currPair.getKey().left != null) {
q.offer(new Pair<>(currPair.getKey().left, currPair.getValue() - 1));
}
if (currPair.getKey().right != null) {
q.offer(new Pair<>(currPair.getKey().right, currPair.getValue() + 1));
}
min = Math.min(min, currPair.getValue());
max = Math.max(max, currPair.getValue());
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = min; i <= max; i++) {
ans.add(new ArrayList<>(colNodesMap.get(i)));
}
return ans;
}
}
|
BFS, 然后我们用map记录遇到的col中node得的值, 因此key-value pair是Integer : List, integer代表col的index, List代表这个col里的nodes的值. 需要注意的是, 我们需要知道col的min和max, 于是我们维护两个变量来知道最左到达哪里(min), 最右到达哪里(max), 然后遍历按照顺序遍历map即可. 这也就是最后一步39, 40行干的事情.
其实一开始我就在想, col以及该col有的nodes知道后, 怎么按照col的index从小到大遍历呢? 本来以为用tree map, 但是感觉有点儿得不偿失, 后来看解析发现要么就是把map中的key set取出来放到list, 然后sort, 最后按照这个sort好的key list去从左到右访问map, 这样就是从小到大. 后来的第二种解法就是我们上面的这个, 只需要知道col的range即可, 把range里面的list从小到大取出来即可, 因为col的index肯定是连续的, tree中没有断枝.
时间复杂度: O(n) n是nodes的个数.
空间复杂度: O(n) n是nodes的个数, 因为可能是perfect tree.
