二叉树垂直遍历是什么？如何用列号和层号给节点排序？

简化版

垂直遍历给根节点列号 0，左孩子列号 -1，右孩子列号 +1；按列从小到大输出，同列内再按层号和题目要求排序。常用 BFS 或 DFS 记录 (col,row,value)，最后按规则分组。

详细版

垂直遍历不是普通层序遍历，它关注节点的横向列位置。

常见规则：

根节点 (row=0, col=0)。
左孩子 (row+1, col-1)。
右孩子 (row+1, col+1)。
最后按 col 分组。
同一列通常按 row 从上到下；如果同 row 同 col，再按值或访问顺序排序，取决于题目。

核心坑是排序规则要问清楚。不同平台的“垂直遍历”和“垂直层序遍历”可能对同坐标节点处理不同。

完整版教学

一、垂直遍历和层序遍历关注点不同

层序遍历按深度分组：第 0 层、第 1 层、第 2 层。垂直遍历按列分组：最左列、中间列、最右列。

给每个节点一个坐标：

root: row=0, col=0
left: row+1, col-1
right: row+1, col+1

这样树上的节点就可以投影到二维网格里。垂直遍历输出的是按 col 分组后的结果。

二、列号如何推导

每向左走一步，列号减 1；每向右走一步，列号加 1。路径决定列号。

例如路径 left -> right -> right，列号变化是：

0 -> -1 -> 0 -> 1

这说明不同路径可能落到同一列，甚至同一行同一列。比如左子树的右孩子和右子树的左孩子都可能在 (row=2,col=0)。

三、为什么要记录 row

只按 col 分组不够，因为同一列里要从上到下输出。row 表示层号，可以确保父层节点排在子层节点前面。

col = 0:
row 0: root
row 2: 某些孙子节点

如果用 DFS 收集节点，不记录 row 就可能因为遍历路径不同导致顺序不稳定。BFS 天然按层访问，但在最终排序或同坐标处理时，row 仍然是清晰依据。

四、同坐标节点怎么处理

不同题目要求不同。有的要求同 row 同 col 按节点值升序；有的按从左到右的访问顺序。这个细节必须看题目。

情况	常见处理
不同 col	col 从小到大
同 col 不同 row	row 从小到大
同 col 同 row	按值或访问顺序

如果题目要求按值排序，收集三元组 (col,row,val) 后全局排序最省心。

五、BFS 和 DFS 怎么选

BFS 适合按层处理，能自然记录 row；DFS 代码也可以，只要把 row 和 col 作为参数传下去。

dfs(node, row, col) {
  if (!node) return;
  list.push([col, row, node.val]);
  dfs(node.left, row + 1, col - 1);
  dfs(node.right, row + 1, col + 1);
}

DFS 后通常排序；BFS 可以边遍历边放入 Map<col, list>，但同坐标排序仍可能需要额外处理。

六、复杂度怎么分析

收集所有节点是 O(n)。如果最终要排序三元组，复杂度是 O(n log n)。如果题目规则较简单，用有序 map 加 BFS 分组，也可能减少显式排序成本，但实现更复杂。

记忆钩子：垂直遍历给树装上坐标轴；col 决定在哪一列，row 决定同列谁在上面。

七、常见误区与追问

误区：垂直遍历就是层序遍历换个输出。 它按列分组，不是按层分组。
误区：只记录 col 就够了。 同列内还要按 row 排序，否则上下顺序会错。
误区：同坐标节点顺序随便。 有些题要求按值升序，有些按访问顺序，必须看清规则。
追问：DFS 可以做吗？ 可以，传递 row/col 收集后排序即可。
追问：复杂度是多少？ 收集 O(n)，排序版通常 O(n log n)，空间 O(n)。

八、加强记忆

垂直遍历的关键是坐标化。根是 (0,0)，左走列减 1，右走列加 1，层数 row 每下去一层加 1。最后按列分组、按层排序、同坐标按题目规则处理。把这套坐标规则说清，比背某个 BFS 模板更稳。

简化版

详细版