LeetCode 987. 二叉树的垂序遍历
题目描述
题意分析
为二叉树节点赋予行列坐标：根在
(0, 0)，左孩子的行加一、列减一，右孩子的行加一、列加一。按列从左到右输出，每一列内部按行从上到下排列；如果多个节点处于同一行同一列，再按节点值从小到大排列。返回按列分组的节点值列表。同一列不同高度的节点不能直接按值排序，同行同列也不能沿用遍历先到先出的顺序。不同节点即使坐标和值都相同，仍分别保留，不进行去重。
解法：坐标采集后排序分组
核心思路
[!blue]
题目对输出提出了三个依次生效的排序条件，可以先完整记录每个节点的坐标和值，再统一排序。这样遍历只负责不漏节点，排序负责最终顺序，两件事不必混在一起处理。
DFS 从根的行列零开始。访问节点时记录三元组
(col, row, value)，再将左孩子坐标更新为(row + 1, col - 1)、右孩子更新为(row + 1, col + 1)。递归参数按行列传递，而记录把列放在第一项，是为了与排序优先级一致。排序先比较列，列不同时由列决定先后；同列再比较行，较浅的节点在前；行也相同时才比较值。这个字典序恰好覆盖题目的全部规则，所以无论 DFS 先收集哪一支，最终结果都一致。
排序完成后，同一列的节点一定连续出现，且列内顺序已经正确。再扫描一次，遇到新列就创建结果组，列相同则追加到当前组。
hasCol用来区分是否已经建立第一组，避免把初始的prevCol = 0错当成已经处理过零列。单用 BFS 虽然能保证先浅后深，却不能保证同层同列时按值递增，因此仍需处理这个最终排序条件。统一收集排序可以直接避免遗漏这一规则。
解题步骤
- 从根坐标开始遍历，收集每个节点的列、行和值。
- 按列升序、行升序、值升序的优先级排序全部记录。
- 初始化空结果和“尚未处理任何列”的标记。
- 依次扫描记录，首次遇到节点或列号变化时创建新组，然后追加当前节点值。
- 返回按列分组的结果。
代码实现
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
List<int[]> nodes = new ArrayList<>();
dfs(root, 0, 0, nodes);
// 按列、行、值依次比较，值只决定同行同列的顺序。
nodes.sort(
(a, b) -> {
if (a[0] != b[0]) {
return Integer.compare(a[0], b[0]);
}
if (a[1] != b[1]) {
return Integer.compare(a[1], b[1]);
}
return Integer.compare(a[2], b[2]);
});
List<List<Integer>> res = new ArrayList<>();
int prevCol = 0;
boolean hasCol = false;
for (int[] node : nodes) {
// 首个节点或列变化时，开启一组结果。
if (!hasCol || node[0] != prevCol) {
res.add(new ArrayList<>());
hasCol = true;
prevCol = node[0];
}
res.get(res.size() - 1).add(node[2]);
}
return res;
}
private void dfs(TreeNode node, int row, int col, List<int[]> nodes) {
if (node == null) {
return;
}
nodes.add(new int[] {
col,
row,
node.val
});
dfs(node.left, row + 1, col - 1, nodes);
dfs(node.right, row + 1, col + 1, nodes);
}
}
import "sort"
func verticalTraversal(root *TreeNode) [][]int {
type item struct {
col int
row int
val int
}
items := make([]item, 0)
var dfs func(node *TreeNode, row, col int)
dfs = func(node *TreeNode, row, col int) {
if node == nil {
return
}
items = append(items, item{col: col, row: row, val: node.Val})
dfs(node.Left, row+1, col-1)
dfs(node.Right, row+1, col+1)
}
dfs(root, 0, 0)
// 按列、行、值依次比较，值只决定同行同列的顺序。
sort.Slice(items, func(i, j int) bool {
if items[i].col != items[j].col {
return items[i].col < items[j].col
}
if items[i].row != items[j].row {
return items[i].row < items[j].row
}
return items[i].val < items[j].val
})
res := make([][]int, 0)
prevCol := 0
hasCol := false
for _, it := range items {
// 首个节点或列变化时，开启一组结果。
if !hasCol || it.col != prevCol {
res = append(res, []int{})
hasCol = true
prevCol = it.col
}
res[len(res)-1] = append(res[len(res)-1], it.val)
}
return res
}
复杂度分析
- 时间复杂度：$O(n\log(n + 1))$。采集和分组各需 $O(n)$，对
n个三元组排序是主要开销。- 空间复杂度：$O(n)$，用于节点记录集合、排序辅助空间和深度不超过
n的递归栈，返回结果也为线性大小。
关键点总结
[!green]
- 比较顺序严格是列、行、值，值仅用于坐标完全相同的节点。
- 采集顺序与输出顺序分开，DFS 或 BFS 都可以负责采集，最终排序规则不能省略。
- 同列记录排序后连续出现，因此只需线性扫描即可分组。
易错点总结
[!yellow]
- 只按列排序，会把同列的上下层次打乱。
- 同列全部按值排序，会把深层的小值放到浅层节点之前，违反行优先规则。
- 依赖 BFS 的先后顺序处理同行同列节点，可能不满足值的升序要求。
- 将左右孩子的列变化写反，会使输出左右列整体颠倒。
- 不单独处理首个分组，而把默认列号当成已有列，可能在结果还为空时就尝试追加。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 314. 二叉树的垂直遍历 | 中等 | 列坐标相同，但本题同一行同一列按值排序，原题保留层序到达的先后。 |
| 102. 二叉树的层序遍历 | 中等 | BFS可得到节点深度，本题还需记录列坐标并处理坐标相同的值排序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！