05 August 2008
这道题跟314的不同之处在于，这道题要计算左右子树的坐标方式，314只管BFS打印出来。
根据题意，需要按照优先级「“列号从小到大”，对于同列节点，“行号从小到大”，对于同列同行元素，“节点值从小到大”」进行答案构造。
因此可以对树进行遍历，遍历过程中记下这些信息 (col, row, val)，然后根据规则进行排序，并构造答案。
先使用「哈希表」进行存储，最后再进行一次性的排序。
时间复杂度：令总节点数量为 n，填充哈希表时进行树的遍历，复杂度为 O(n)；构造答案时需要进行排序，复杂度为 O(nlogn)。整体复杂度为O(nlogn)
空间复杂度：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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
public List<List<Integer>> verticalTraversal(TreeNode root) {
map.put(root, new int[]{0, 0, root.val});
dfs(root);
List<int[]> list = new ArrayList<>(map.values());
list.sort((a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
int len = list.size();
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < len; ) {
int j = i;
List<Integer> tmp = new ArrayList<>();
while (j < len && list.get(j)[0] == list.get(i)[0]) tmp.add(list.get(j++)[2]);
ans.add(tmp);
i = j;
}
return ans;
}
void dfs(TreeNode root) {
if (root == null) {
return;
}
int[] info = map.get(root);
int col = info[0], row = info[1], val = info[2];
if (root.left != null) {
map.put(root.left, new int[]{col - 1, row + 1, root.left.val});
dfs(root.left);
}
if (root.right != null) {
map.put(root.right, new int[]{col + 1, row + 1, root.right.val});
dfs(root.right);
}
}
}
最终要让所有节点的相应信息有序，可以使用「优先队列（堆）」边存储边维护有序性。
时间复杂度：令总节点数量为 n，将节点信息存入优先队列（堆）复杂度为 O(nlogn)；构造答案复杂度为 O(nlogn)。整体复杂度为 O(nlogn)
空间复杂度：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
26
27
28
29
30
31
32
33
34
class Solution {
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> { // col, row, val
if (a[0] != b[0]) return a[0] - b[0];
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
public List<List<Integer>> verticalTraversal(TreeNode root) {
int[] info = new int[]{0, 0, root.val};
queue.add(info);
dfs(root, info);
List<List<Integer>> ans = new ArrayList<>();
while (!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
int[] poll = queue.peek();
while (!queue.isEmpty() && queue.peek()[0] == poll[0]) tmp.add(queue.poll()[2]);
ans.add(tmp);
}
return ans;
}
void dfs(TreeNode root, int[] fa) {
if (root.left != null) {
int[] linfo = new int[]{fa[0] - 1, fa[1] + 1, root.left.val};
queue.add(linfo);
dfs(root.left, linfo);
}
if (root.right != null) {
int[] rinfo = new int[]{fa[0] + 1, fa[1] + 1, root.right.val};
queue.add(rinfo);
dfs(root.right, rinfo);
}
}
}
当然，如果想锻炼一下自己的代码能力，不使用三元组 (col, row, val)(col,row,val) 进行存储，而是使用哈希表嵌套，也是可以的。
用三个「哈希表」来记录相关信息：
使用 node2row 和 node2col 分别用来记录「节点到行」&「节点到列」的映射关系，并实现 dfs1 对树进行遍历，目的是为了记录下相关的映射关系；
使用 col2row2nodes 记录「从列到行，从行到节点集」的映射关系，具体的存储格式为 {col : {row : [node1, node2, … ]}}，实现 dfs2 再次进行树的遍历，配合之前 node2row 和 node2col信息，填充 col2row2nodes 的映射关系；
按照题意，按「列号从小到大」，对于同列节点，按照「行号从小到大」，对于同列同行元素，按照「节点值从小到大」的规则，使用 col2row2nodes + 排序 构造答案。
注意：本解法可以只进行一次树的遍历，分两步主要是不想 dfs 操作过于复杂，加大读者的阅读难度，于是在拆开不影响复杂度上界的情况，选择了分两步。
时间复杂度：令总的节点数量为 n，填充几个哈希表的复杂度为 O(n)；构造答案时需要对行号、列号和节点值进行排序，总的复杂度上界为 O(nlogn)。整体复杂度为 O(nlogn)
空间复杂度：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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
Map<TreeNode, Integer> node2col = new HashMap<>(), node2row = new HashMap<>();
Map<Integer, Map<Integer, List<Integer>>> col2row2nodes = new HashMap<>();
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
node2col.put(root, 0);
node2row.put(root, 0);
dfs1(root);
dfs2(root);
List<Integer> cols = new ArrayList<>(col2row2nodes.keySet());
Collections.sort(cols);
for (int col : cols) {
Map<Integer, List<Integer>> row2nodes = col2row2nodes.get(col);
List<Integer> rows = new ArrayList<>(row2nodes.keySet());
Collections.sort(rows);
List<Integer> cur = new ArrayList<>();
for (int row : rows) {
List<Integer> nodes = row2nodes.get(row);
Collections.sort(nodes);
cur.addAll(nodes);
}
ans.add(cur);
}
return ans;
}
// 树的遍历，根据「节点到列」&「节点到行」的映射关系，构造出「从列到行，从行到节点集」的映射关系
void dfs2(TreeNode root) {
if (root == null) return ;
int col = node2col.get(root), row = node2row.get(root);
Map<Integer, List<Integer>> row2nodes = col2row2nodes.getOrDefault(col, new HashMap<>());
List<Integer> nodes = row2nodes.getOrDefault(row, new ArrayList<>());
nodes.add(root.val);
row2nodes.put(row, nodes);
col2row2nodes.put(col, row2nodes);
dfs2(root.left);
dfs2(root.right);
}
// 树的遍历，记录下「节点到列」&「节点到行」的映射关系
void dfs1(TreeNode root) {
if (root == null) return ;
if (root.left != null) {
int col = node2col.get(root);
node2col.put(root.left, col - 1);
int row = node2row.get(root);
node2row.put(root.left, row + 1);
dfs1(root.left);
}
if (root.right != null) {
int col = node2col.get(root);
node2col.put(root.right, col + 1);
int row = node2row.get(root);
node2row.put(root.right, row + 1);
dfs1(root.right);
}
}
}