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, x1, y-1) dfs(root.Right, x1, y1) } 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)出发递归时左子树(x1, y-1)、右子树(x1, y1)与题目定义完全吻合dfs(root, 0, 0) // 递归内部 nodes append(nodes, node{x, y, root.Val}) dfs(root.Left, x1, y-1) dfs(root.Right, x1, y1)这里需要注意仓库实现使用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），仅供参考
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, x1, y-1) dfs(root.Right, x1, y1) } 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)出发递归时左子树(x1, y-1)、右子树(x1, y1)与题目定义完全吻合dfs(root, 0, 0) // 递归内部 nodes append(nodes, node{x, y, root.Val}) dfs(root.Left, x1, y-1) dfs(root.Right, x1, y1)这里需要注意仓库实现使用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），仅供参考
)
)
