LeetCode 987. 二叉树的垂序遍历 堆题解，本题可使用有序结构，也可以对统计数组直接排序。
987. 二叉树的垂序遍历#
https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
统计+堆结构#
先看示例：
官方示例已经疯狂暗示我们了，我们需要x,y信息：
- 我们记录每个节点的横坐标，以root为0，root.left为-1，root.right为1。题干中要求对同行同列的值进行大小排序，因此我们同时记录纵坐标。
- 同时，以横坐标为
groupByKey组织节点数据。
- 最后，从最左的横坐标开始输出节点数据。
复杂度分析#
先遍历一次树统计节点信息，又从统计的map中取出数据，同时内部使用了一个堆结构，复杂度主要体现在：
- 遍历
n个元素；
- 对
n个元素入堆，建堆复杂度n；
- 从堆中取出元素，堆化复杂度
n*logn；
整体时间复杂度O(n+n*logn)，可省略低阶。
额外空间我们借助一个map统计节点信息，内部持有了一个总量为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
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
/*
* 执行用时：
* 2 ms
* , 在所有 Java 提交中击败了
* 98.32%
* 的用户
* 内存消耗：
* 41.6 MB
* , 在所有 Java 提交中击败了
* 39.93%
* 的用户
* 通过测试用例：
* 32 / 32
*/
/**
* 结果数组
*/
List<List<Integer>> ans;
/**
* key为横坐标的map，统计节点遍历情况
* 优先级有序队列中存：x、y、val
*/
Map<Integer, Queue<int[]>> x2Nodes;
/**
* 记录横坐标边界
*/
int leftMostIdx;
int rightMostIdx;
/**
* 基本思路：
* 我们记录每个节点的横坐标，以root为0，root.left为-1，root.right为1。题干中要求对同行同列的值进行大小排序，因此我们同时记录纵坐标。
* 同时，以横坐标为groupByKey组织节点数据
* 最后，从最左的横坐标开始输出节点数据
*/
public List<List<Integer>> verticalTraversal(TreeNode root) {
x2Nodes = new HashMap<>();
dfs(root, 0, 0);
ans = new ArrayList<>();
for (int i = leftMostIdx; i <= rightMostIdx; i++) {
if (!x2Nodes.containsKey(leftMostIdx)) {
continue;
}
List<Integer> valList = new ArrayList<>();
Queue<int[]> nodeQueue = x2Nodes.get(i);
while (!nodeQueue.isEmpty()) {
valList.add(nodeQueue.poll()[2]);
}
ans.add(valList);
}
return ans;
}
private void dfs(TreeNode node, int x, int y) {
if (node == null) {
return;
}
x2Nodes.putIfAbsent(x, new PriorityQueue<>((a, b) -> {
if (a[1] != b[1]) {
// 先以y坐标升序
return a[1] - b[1];
}
// 再以val升序
return a[2] - b[2];
}));
Queue<int[]> queue = x2Nodes.get(x);
queue.offer(new int[]{x, y, node.val});
leftMostIdx = Math.min(leftMostIdx, x);
rightMostIdx = Math.max(rightMostIdx, x);
dfs(node.left, x - 1, y + 1);
dfs(node.right, x + 1, y + 1);
}
|
统计+排序#
受官解思路启发，其实我们直接用一个数组统计节点信息，然后对其排序即可，这样代码简洁点。
复杂度分析#
整体复杂度与解法1一致。
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
57
58
59
60
61
62
63
64
65
66
67
68
|
static class Sort {
/**
* 执行用时：
* 2 ms
* , 在所有 Java 提交中击败了
* 98.32%
* 的用户
* 内存消耗：
* 41.6 MB
* , 在所有 Java 提交中击败了
* 44.80%
* 的用户
* 通过测试用例：
* 32 / 32
*/
// 直接用list统计每个节点的x、y、val
List<int[]> nodes;
public List<List<Integer>> verticalTraversal(TreeNode root) {
nodes = new ArrayList<>();
dfs(root, 0, 0);
// 对统计好的数据排序，先用x排序，再用y值排序，最后用val排序
nodes.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];
});
if (nodes.isEmpty()) {
return Collections.emptyList();
}
List<List<Integer>> ans = new ArrayList<>();
// 上一个横坐标
int prevXIdx = Integer.MIN_VALUE;
// i表示ans位置
int i = -1;
// j表示nodes位置
int j = 0;
while (j < nodes.size()) {
// 当前横坐标刚开始消费，添加新的innerList
if (prevXIdx != nodes.get(j)[0]) {
ans.add(new ArrayList<>());
i++;
}
ans.get(i).add(nodes.get(j)[2]);
prevXIdx = nodes.get(j)[0];
j++;
}
return ans;
}
private void dfs(TreeNode node, int x, int y) {
if (node == null) {
return;
}
nodes.add(new int[]{x, y, node.val});
dfs(node.left, x - 1, y + 1);
dfs(node.right, x + 1, y + 1);
}
}
|