LeetCode-Go 题解：二叉树垂序遍历（987. Vertical Order Traversal of a Binary Tree）
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
本篇技术指南围绕 LeetCode 987 题「二叉树的垂序遍历」（Vertical Order Traversal of a Binary Tree）展开，以 leetcode/0987.Vertical-Order-Traversal-of-a-Binary-Tree/README.md 中的官方题解为主体，结合 LeetCode-Go 仓库中该题的 源码实现 与 单元测试 进行源码级佐证。读完本文，你将掌握「给二叉树节点标定二维坐标 → 按列分组 → 坐标内按值排序」的完整解题范式，理解排序规则的精确写法，并能独立用 Go 复现这一算法。
题目与坐标定义
给定一棵二叉树的根节点root，计算该二叉树的垂序遍历（vertical order traversal）序列。
题目用二维坐标(row, col)描述每个节点的位置：
- 根节点位于
(0, 0)； - 对于位于
(row, col)的节点，其左子节点位于(row + 1, col - 1)，右子节点位于(row + 1, col + 1)。
垂序遍历的返回结果是一个列表：从最左边一列开始、到最右边一列结束，每一列中的节点按照从上到下的顺序排列；若同一行同一列（即同一坐标）上存在多个节点，则按节点值从小到大排序。
约束条件：
- 节点数量范围为
[1, 1000]； - 节点值范围为
0 <= Node.val <= 1000。
示例一
Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation: Column -1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.节点 3 位于(0, 0)，节点 9 位于(1, -1)，节点 20 位于(1, 1)，节点 15 位于(2, 0)，节点 7 位于(2, 2)。第 0 列中有节点 3（第 0 行）和节点 15（第 2 行），按从上到下顺序输出[3, 15]。
示例二（同一坐标多节点）
Input: root = [1,2,3,4,5,6,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: Column -2: Only node 4 is in this column. Column -1: Only node 2 is in this column. Column 0: Nodes 1, 5, and 6 are in this column. 1 is at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we order them by their value, 5 before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.该示例的关键在于：节点 5 和节点 6 都位于坐标(2, 0)，二者既同行又同列，因此必须按值排序，5排在6之前，于是第 0 列输出[1, 5, 6]。
示例三（验证排序的稳定性语义）
Input: root = [1,2,3,4,6,5,7] Output: [[4],[2],[1,5,6],[3],[7]] Explanation: This case is the exact same as example 2, but with nodes 5 and 6 swapped. Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.示例三把示例二中的节点 5、6 互换位置，但二者坐标均为(2, 0)，最终结果不变——这组对照用例清晰地验证了「同一坐标按值排序」这一规则，也直接对应测试文件中三个用例的第三组。
解题思路：两大核心问题
题目要求一列一列地遍历二叉树，解题前必须先解决两个问题：
- 坐标计算：如何确定二叉树上每个节点的二维坐标
(row, col)？ - 同坐标排序：同一个二维坐标点上「摞起来」多个节点时，如何保证输出顺序？
原题解给出的思路分三步：
- 第一步（求坐标）：题目规定根节点为原点
(0, 0)，因此左子树的列坐标（col）均为负数，右子树的列坐标均为正数。使用先序遍历（DFS），即可为每个节点标定出二维坐标。 - 第二步（排序）：对节点数组做一次排序——先按列坐标从小到大排；列坐标相同的（即摞在同一坐标列上的节点），按行坐标从上到下排；行坐标也相同的，按节点值
val从小到大排。排序完成，两个问题同时解决。 - 第三步（分组输出）：扫描一遍排好序的数组，按列依次把同一列的节点打包进一个一维数组，最终得到二维数组即为所求。
排序规则之所以能一步到位，是因为它把「列分组」「行顺序」「值排序」三级次序编码进了同一个比较函数，这与 LeetCode 官方要求的排序语义完全一致：先列、再行、最后值。
Go 源码实现精讲
以下是 987. Vertical Order Traversal of a Binary Tree.go 中的完整实现：
package leetcode import ( "math" "sort" "github.com/halfrost/LeetCode-Go/structures" ) // TreeNode define type TreeNode = structures.TreeNode type node struct { x, y, val int } func verticalTraversal(root *TreeNode) [][]int { var dfs func(root *TreeNode, x, y int) var nodes []node dfs = func(root *TreeNode, x, y int) { if root == nil { return } nodes = append(nodes, node{x, y, root.Val}) dfs(root.Left, x+1, y-1) dfs(root.Right, x+1, y+1) } dfs(root, 0, 0) sort.Slice(nodes, func(i, j int) bool { a, b := nodes[i], nodes[j] return a.y < b.y || a.y == b.y && (a.x < b.x || a.x == b.x && a.val < b.val) }) var res [][]int lastY := math.MinInt32 for _, node := range nodes { if lastY != node.y { res = append(res, []int{node.val}) lastY = node.y } else { res[len(res)-1] = append(res[len(res)-1], node.val) } } return res }结构与坐标标注（DFS）
自定义结构体node保存三个字段：x（行，对应题目中的 row）、y（列，对应题目中的 col）、val（节点值）。
type node struct { x, y, val int }先序遍历从根节点(0, 0)出发，递归时左子树(x+1, y-1)、右子树(x+1, y+1)，与题目定义完全吻合：
dfs(root, 0, 0) // 递归内部 nodes = append(nodes, node{x, y, root.Val}) dfs(root.Left, x+1, y-1) dfs(root.Right, x+1, y+1)这里需要注意：仓库实现使用x表示行、y表示列，与数学直觉相反，但和原题解中「先序遍历计算二维坐标」的叙述保持一致——y才是最终分组依据（列），这一点在阅读源码时容易混淆，特此说明。
三级排序规则
sort.Slice的比较函数把排序语义编码为：
return a.y < b.y || a.y == b.y && (a.x < b.x || a.x == b.x && a.val < b.val)展开后的优先级为：
a.y < b.y：列坐标小的在前，实现「从左到右」；- 列相等时
a.x < b.x：行坐标小的在前，实现「从上到下」； - 行列都相等时
a.val < b.val：节点值小的在前，处理「同一坐标摞多个节点」的情况。
由于 Go 中&&的优先级高于||，该表达式实际等价于a.y < b.y || (a.y == b.y && (a.x < b.x || (a.x == b.x && a.val < b.val)))，三级比较链书写紧凑且无歧义。
按列打包输出
排序完成后，数组已按「列 → 行 → 值」有序。只需一次线性扫描，借助lastY记录当前列号即可完成分组：
var res [][]int lastY := math.MinInt32 for _, node := range nodes { if lastY != node.y { res = append(res, []int{node.val}) lastY = node.y } else { res[len(res)-1] = append(res[len(res)-1], node.val) } }当列号变化时新开一个一维数组；列号不变时把值追加到最后一个分组。lastY初始化为math.MinInt32保证首个节点必然触发新分组，因为题目约束Node.val >= 0，实际列号不会小于该哨兵值。整个算法的时间复杂度为 O(n log n)（排序主导），空间复杂度为 O(n)，其中 n 为节点总数。
测试用例与仓库数据结构佐证
测试用例解析
该题在仓库中对应的测试文件为 987. Vertical Order Traversal of a Binary Tree_test.go，测试用例与题解中的三个示例一一对应：
| 输入（层序数组） | 期望输出 | 说明 |
|---|---|---|
[3,9,20,null,null,15,7] | [[9],[3,15],[20],[7]] | 基础场景，验证按列输出 |
[1,2,3,4,5,6,7] | [[4],[2],[1,5,6],[3],[7]] | 同一坐标(2,0)上 5、6 按值排序 |
[1,2,3,4,6,5,7] | [[4],[2],[1,5,6],[3],[7]] | 5、6 位置互换，结果不变，验证值排序语义 |
测试框架采用「参数 + 期望答案」的结构化组织方式：para987持有层序数组输入，ans987持有期望的二维数组输出，二者组合成question987后批量断言，并打印输入输出便于人工核对：
qs := []question987{ { para987{[]int{3, 9, 20, structures.NULL, structures.NULL, 15, 7}}, ans987{[][]int{{9}, {3, 15}, {20}, {7}}}, }, // ... } for _, q := range qs { _, p := q.ans987, q.para987 fmt.Printf("【input】:%v ", p) root := structures.Ints2TreeNode(p.one) fmt.Printf("【output】:%v \n", verticalTraversal(root)) }复用的二叉树工具库
实现与测试都依赖仓库统一的二叉树辅助包 structures/TreeNode.go，其中的关键设施：
type TreeNode struct定义了标准二叉树节点（Val、Left、Right三字段），源码文件中通过type TreeNode = structures.TreeNode类型别名直接复用，无需重复定义；- 常量
NULL = -1 << 63用于在层序数组中标记空节点，测试用例里出现的structures.NULL即指它； - 函数
Ints2TreeNode(ints []int)把 LeetCode 风格的层序数组还原为真正的*TreeNode树结构，是测试中structures.Ints2TreeNode(p.one)调用的底层实现，其构造逻辑采用队列逐层建树，遇到NULL则跳过对应子节点。
这套工具函数在整个 LeetCode-Go 仓库的二叉树类题目中被广泛复用，保证所有题解共享同一套树结构与序列化约定。
变体与延伸思考
垂序遍历是二叉树遍历家族中的一个重要变体，理解它有助于触类旁通：
- 与层序遍历的关系：层序遍历（level order）只关心行，垂序遍历在行的基础上增加了列维度的分组，可以视为层序遍历的二维推广；
- 与 Top-down / Bottom-up 遍历的区别：传统 DFS 只记录访问顺序，而垂序遍历要求先建立节点的几何坐标模型，再按坐标多级排序，这要求我们在遍历之外额外维护一个「坐标 → 节点」的映射；
- 工程化替代方案：本题的排序解法简洁直观；若追求更严格的「按行从上到下」语义而不依赖全量排序，也可以先用 DFS 收集坐标信息，再使用哈希表（map[列号][]节点）按列聚合，最后对每列内部按 (行, 值) 排序输出，两种思路复杂度同为 O(n log n)，但排序解法代码更短、更不易出错。
小结
LeetCode 987 的核心方法论可以概括为三步：先序遍历标定坐标 → 按「列、行、值」三级排序 → 线性扫描按列打包。仓库中的 Go 实现将这三步浓缩在 30 余行代码中，配合三组覆盖不同排序场景的测试用例，完整验证了算法的正确性。无论是应对面试手写，还是在 LeetCode-Go 仓库中研读其它树形遍历题目，这套「坐标建模 + 多级排序」的思路都值得复用。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
