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
| class Solution {
Map<Integer, ArrayList<Pair<Integer, Integer>>> columnTable = new HashMap();
int minColumn = 0, maxColumn = 0;
private void DFS(TreeNode node, Integer row, Integer column) {
if (node == null)
return;
if (!columnTable.containsKey(column)) {
this.columnTable.put(column, new ArrayList<Pair<Integer, Integer>>());
}
this.columnTable.get(column).add(new Pair<Integer, Integer>(row, node.val));
this.minColumn = Math.min(minColumn, column);
this.maxColumn = Math.max(maxColumn, column);
this.DFS(node.left, row + 1, column - 1);
this.DFS(node.right, row + 1, column + 1);
}
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> output = new ArrayList();
if (root == null) {
return output;
}
this.DFS(root, 0, 0);
for (int i = minColumn; i < maxColumn + 1; ++i) {
Collections.sort(columnTable.get(i),
(p1, p2) -> p1.getKey() != p2.getKey() ? p1.getKey() - p2.getKey() : p1.getValue() - p2.getValue());
List<Integer> sortedColumn = new ArrayList();
for (Pair<Integer, Integer> p : columnTable.get(i)) {
sortedColumn.add(p.getValue());
}
output.add(sortedColumn);
}
return output;
}
}
|
DFS去做. dfs也是每个level的最左边先被traverse到, 其次是第二靠左以此类推. 从level order traversal就能知道.
比较神奇的是这个sort能把大家的相对位置保持住. 比如有个node A在上方都是后来才被visit到, 而同一个col中有一个更深的node B先被visit了. 然后还有一个node C是在visitA后也被visit到, 只不过和B是重合的. 那么顺序就是B A C. 我们根据row一排序就会变为A B C, 它不会是A C B就很好. 也就是在同一个row同一个col的nodes的相对位置不会改变(默认是靠左的node在前, 靠右的node在后), 除非是右边的node的val更小, 那么它就会跑到左边node前面.
时间复杂度: O(N) + O(m * (k + klogk)) m是col的个数, k是装最多元素的col的元素个数. 因为每个col我们都要sort, sort完还要把sort好的元素装入output中.
空间复杂度: O(N) 就是map存每个col的node, 同时装答案也要分配空间.
BFS的话不仅要记录row, 还有记录col, 因此是Pair<TreeNode, Pair<Integer, Integer>>这样的形式.
