LeetCode 314. 二叉树的垂直遍历
目录
题目描述
题意分析
把二叉树画在平面上，根节点占一列，往左走一步就落到左边相邻的一列，往右走一步就落到右边相邻的一列。要求按列从最左到最右输出，每一列内部的节点从上到下排列。
关键在于「列」这个坐标不是树本身自带的属性，需要我们在遍历时自己带下去：根记 0，左孩子记
col - 1，右孩子记col + 1。同一列可能来自树中完全不相邻的两棵子树，所以必须有一个以列号为键的容器把它们收集到一起。题面对同列内部的顺序有明确规定：先按深度从上到下，深度相同时按从左到右。这句话是整道题的算法信号——它描述的正是层序扩散的顺序，意味着只要遍历顺序本身满足「先浅后深、同深先左」，把节点值直接追加到所属列的尾部就自动是对的，不需要任何排序。反过来，如果遍历顺序不满足这个性质，就得额外记录深度并做稳定排序，代码会复杂得多。
还有一个容易被忽略的信号：列号可正可负，不能直接当数组下标用，要么用哈希表，要么先做偏移。输出时列号必须连续覆盖从最小到最大的范围，而不是按插入顺序或哈希顺序。
边界：根为空时返回空列表；只有一条左链的退化树会让最小列号一路变负；节点值本身允许为负，不能拿值当哨兵。
解法：BFS 按列分组
核心思路
先看暴力想法：先跑一遍 DFS，把每个节点记成三元组
(列号, 深度, 值)存进一个大列表，最后按「列号升序、深度升序」排序再分组输出。这个做法是对的，但排序带来 $O(n \log n)$，而且必须显式记录深度、必须保证排序稳定否则同深度节点的左右顺序会乱。瓶颈就在这里：我们为一个本来可以「顺手生成」的顺序付出了排序代价。观察题面对顺序的要求——同列内先按深度、深度相同按从左到右——这恰好就是 BFS 出队的顺序。BFS 按层推进保证了浅的节点先出队，同一层内如果入队时坚持「先左孩子后右孩子」，出队顺序也就自左向右。于是深度这个维度根本不需要记录，更不需要排序。
由此得到这个解法的不变量：在 BFS 的任意时刻，对每个列号
c，colToValues[c]中已有的节点恰好是所有已出队且列号为c的节点，且它们的排列顺序就是题目要求的最终顺序。换句话说，每次出队时直接append到对应列的尾部，这个列表从头到尾都不需要回头调整。剩下的就是「怎么把列号带下去」。BFS 队列里存的不能只是节点，还得带上它的列号，所以用两个平行队列（Java）或一个
{节点, 列号}结构体队列（Go）。同时在出队时顺手维护minCol与maxCol，最后从minCol到maxCol逐列取出即可。这里有个隐含但重要的性质：从根（列 0）走到任意节点，列号每步只变化 1，所以[minCol, maxCol]之间的每个整数都必然被某个节点占据，遍历区间时不会取到空列。
解题步骤
- 根为空直接返回空列表。为什么：后续逻辑无条件地把根入队，若不拦截会对空指针取
val。这也是唯一需要的特判。- 准备哈希表
colToValues、节点队列、列号队列，把根与列号 0 一起入队。为什么用哈希表而不是数组：列号可以是负数，且范围事先未知，哈希表免去了估算偏移量的麻烦。- 循环出队，取出节点与它配对的列号。为什么两个队列要同步
poll：它们是一一对应的平行结构，任何一次只弹其中之一都会让后续所有配对错位。- 把节点值追加到
colToValues[col]的尾部，并用col更新minCol/maxCol。为什么可以直接追加不排序：由上面的不变量，BFS 出队顺序已经等于题目要求的顺序。- 左孩子存在则以
col - 1入队，右孩子存在则以col + 1入队，且必须先左后右。为什么顺序不能反：同一层同一列若同时有两个节点，入队顺序决定了它们的出队顺序，写反会让左右颠倒。- BFS 结束后从
minCol遍历到maxCol，依次把每列的列表加入结果。为什么不能直接遍历哈希表：哈希表的迭代顺序与列号大小无关，结果的列顺序会是乱的。以
具体用例 root = [3,9,20,null,null,15,7]走一遍。这棵树是根 3，左孩子 9，右孩子 20，20 的左右孩子分别是 15 和 7。初始：队列
[(3, col=0)]，minCol = maxCol = 0，哈希表为空。
第一次出队(3, 0)：colToValues[0] = [3]，minCol = maxCol = 0。左孩子 9 以列 -1 入队，右孩子 20 以列 1 入队，队列变为[(9,-1), (20,1)]。
第二次出队(9, -1)：colToValues[-1] = [9]，minCol更新为 -1。9 无孩子。
第三次出队(20, 1)：colToValues[1] = [20]，maxCol更新为 1。左孩子 15 以列1 - 1 = 0入队，右孩子 7 以列1 + 1 = 2入队，队列变为[(15,0), (7,2)]。
第四次出队(15, 0)：列 0 已存在列表[3]，追加后变为[3, 15]。注意 15 比 3 深，正因为 BFS 保证浅节点先出队，追加到尾部就是正确的上下顺序。
第五次出队(7, 2)：colToValues[2] = [7]，maxCol更新为 2。队列空，循环结束。
收尾：从 -1 遍历到 2，依次取出[9]、[3,15]、[20]、[7]，最终答案[[9],[3,15],[20],[7]]。
代码实现
class Solution {
// 题目要求同一列从上到下输出。
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Map<Integer, List<Integer>> colToValues = new HashMap<>();
Queue<TreeNode> nodeQueue = new ArrayDeque<>();
Queue<Integer> colQueue = new ArrayDeque<>();
nodeQueue.offer(root);
colQueue.offer(0);
int minCol = 0;
int maxCol = 0;
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
int col = colQueue.poll();
colToValues.computeIfAbsent(col, key -> new ArrayList<>()).add(node.val);
minCol = Math.min(minCol, col);
maxCol = Math.max(maxCol, col);
if (node.left != null) {
nodeQueue.offer(node.left);
colQueue.offer(col - 1);
}
if (node.right != null) {
nodeQueue.offer(node.right);
colQueue.offer(col + 1);
}
}
for (int col = minCol; col <= maxCol; col++) {
res.add(colToValues.get(col));
}
return res;
}
}
func verticalOrder(root *TreeNode) [][]int {
// 题目要求同一列从上到下输出。
res := make([][]int, 0)
if root == nil {
return res
}
type item struct {
node *TreeNode
col int
}
colToValues := make(map[int][]int)
queue := make([]item, 0)
queue = append(queue, item{node: root, col: 0})
minCol, maxCol := 0, 0
for head := 0; head < len(queue); head++ {
cur := queue[head]
node := cur.node
col := cur.col
colToValues[col] = append(colToValues[col], node.Val)
if col < minCol {
minCol = col
}
if col > maxCol {
maxCol = col
}
if node.Left != nil {
queue = append(queue, item{node: node.Left, col: col - 1})
}
if node.Right != nil {
queue = append(queue, item{node: node.Right, col: col + 1})
}
}
for col := minCol; col <= maxCol; col++ {
res = append(res, colToValues[col])
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点恰好入队一次、出队一次，出队时做的是一次哈希表追加与两次比较，均摊常数；末尾按列号收集的循环长度等于列数，不超过 $n$。凭什么不是 $O(n \log n)$：因为顺序由 BFS 直接产出，全程没有排序。
- 空间复杂度：$O(n)$。哈希表总共存放 $n$ 个节点值，队列在最宽一层的规模上界也是 $O(n)$（完全二叉树时最后一层约 $n/2$ 个节点同时在队）。凭什么不能更小：答案本身就要输出全部 $n$ 个值。
关键点总结
- 让遍历顺序替你完成排序。当题面对输出顺序的描述恰好等于某种遍历的天然顺序时，选对遍历方式就能省掉一次排序和一个维度的状态，这是树与图题里最值钱的一类观察。
- 坐标要随节点一起在队列中传递。凡是「节点自身不携带、但由路径决定」的信息（列号、深度、路径和），都应作为队列元素的一部分，而不是事后重算。
- 可负的键用哈希表，输出时再按序遍历键的区间。不要指望哈希表的迭代顺序，最终顺序必须由显式的
minCol → maxCol循环给出。- 先左后右的入队顺序是语义的一部分，不是风格问题；它承载了「同层同列时左边优先」这条规则。
- 面试视角：面试官问到这题，通常会紧接着追问「如果同列同层还要按节点值从小到大排呢」。这正是 987. 二叉树的垂序遍历 的加强要求，此时 BFS 的天然顺序不再够用，必须退回到「收集三元组 + 自定义比较器排序」的方案。能主动说清「314 靠遍历顺序、987 必须排序」这条分界线，比写出代码更能体现理解深度。
易错点总结
- 错误写法：最后直接
for (List<Integer> v : colToValues.values()) res.add(v)→ 用例[3,9,20,null,null,15,7]，HashMap的迭代顺序按哈希值而非列号，可能输出[[3,15],[9],[20],[7]]，列的左右次序完全错乱。- 错误写法：把列号当数组下标写成
res[col]→ 用例[1,2,null,3]这条左斜链会产生列号 -1、-2，负下标直接数组越界异常。- 错误写法：入队时先右后左 → 用例
[1,2,3,4,5,6,7]，节点 5 与 6 同层同列 0，先右后左会让输出的列 0 变成[1,6,5]而不是正确的[1,5,6]。- 错误写法：只弹节点队列忘了同步弹列号队列 → 任意含两层以上的树，第二次出队起节点与列号就错位，所有节点被归到错误的列。
- 错误写法：改用 DFS 前序递归并直接追加到列表 → 用例
[3,9,8,4,0,1,7]，DFS 会先把左子树整条深路径写完再回头处理右子树，同一列里深层节点排到了浅层节点前面，上下顺序错误。- 错误写法：
minCol/maxCol初始化为Integer.MAX_VALUE与Integer.MIN_VALUE却在根为空时跳过更新 → 空树若没有提前返回，末尾循环会从MAX_VALUE跑到MIN_VALUE，虽然不进循环但把minCol参与运算的写法极易溢出。- 错误写法：用节点值 0 或 -1 当作「无孩子」的标记 → 用例
[0,-1,null]，题目允许节点值取 0 和负数，用值判空会漏掉真实存在的孩子。- 错误写法：末尾用
colToValues.get(col)却对区间内某列做了非空判断后continue→ 逻辑上多余，且一旦误写成跳过就会让结果少一列；实际上[minCol, maxCol]中每列必然非空，因为列号沿根到节点的路径每步只变动 1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 987. 二叉树的垂序遍历 | 困难 | 同列同深度还要按节点值升序，BFS 的天然顺序失效，必须收集三元组后自定义排序 |
| 102. 二叉树的层序遍历 | 中等 | 只按行分组不按列，队列里不用带坐标，改为按层批量出队 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 在层序基础上按奇偶层反向拼接，考的是输出顺序的后处理 |
| 199. 二叉树的右视图 | 中等 | 只取每层最后一个节点，需要显式的层边界而非列号 |
| 662. 二叉树最大宽度 | 中等 | 带下去的是完全二叉树编号而非列号，重点是防止编号溢出 |
| 515. 在每个树行中找最大值 | 中等 | 层内做聚合取最大值，不保留层内全部元素 |
| 513. 找树左下角的值 | 中等 | 反过来先右后左入队，最后一个出队的即为答案，是入队顺序的另一种用法 |