二叉树的垂直遍历（Vertical Order Traversal of a Binary Tree）

题目描述
给定一棵二叉树的根节点，你需要对这棵树进行“垂直遍历”，并返回结果。垂直遍历的规则如下：

• 假设根节点的位置为(0, 0)。
• 对于任意一个节点，如果它的位置是(x, y)，那么它的左子节点的位置是(x-1, y+1)，右子节点的位置是(x+1, y+1)。
• 垂直遍历意味着我们需要按照节点所在的“垂直列”x的值从小到大的顺序，输出每一列中的节点值。
• 对于同一列x内的节点，如果它们在同一行y，则按照节点值从小到大排序（这是常见的变体要求，有时也可能要求按出现顺序，这里我们采用普遍的标准做法：先按y排序，同y再按值排序）。

例如，对于二叉树：

       3
      / \
     9   20
        /  \
       15   7

垂直遍历的结果为：[[9], [3, 15], [20], [7]]。

解题过程循序渐进讲解

步骤1：理解位置映射
首先我们需要建立节点位置(x, y)与节点值之间的映射。根据规则：

• 根节点3在(0,0)。
• 左子节点9在(0-1, 0+1) = (-1,1)。
• 右子节点20在(0+1, 0+1) = (1,1)。
• 节点20的左子节点15在(1-1, 1+1) = (0,2)。
• 节点20的右子节点7在(1+1, 1+1) = (2,2)。

按列x分组：

• 列x=-1: 节点9 (位置(-1,1))。
• 列x=0: 节点3 (位置(0,0))，节点15 (位置(0,2))。
• 列x=1: 节点20 (位置(1,1)）。
• 列x=2: 节点7 (位置(2,2))。

然后对每一列内的节点，先按行y从小到大排序，如果y相同再按节点值从小到大排序。这里x=0列有两个节点，它们的y分别是0和2，已经按y排好序，所以顺序是[3,15]。其他列只有一个节点。因此最终结果为[[9], [3,15], [20], [7]]。

步骤2：选择数据结构来存储映射
我们需要一个能按x列分组，并且每组内能存储节点(y, 值)的数据结构，以便后续排序。常用选择：

• 使用字典（哈希表），键为x（列索引），值为一个列表，列表中每个元素是(y, 节点值)。
• 由于我们需要最终按x从小到大的顺序输出，而x可能为负数，所以遍历完字典后，需要将键排序。

步骤3：遍历树以收集节点信息
我们可以通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历树，在访问每个节点时，记录其(x, y)和节点值，并存入上述字典中。

这里以DFS为例，从根节点(0,0)开始递归：

• 访问当前节点，将(y, 节点值)加入字典中键为x的列表。
• 递归遍历左子节点，传入位置(x-1, y+1)。
• 递归遍历右子节点，传入位置(x+1, y+1)。

步骤4：对每列内的节点进行排序
遍历完成后，字典中每个键x对应一个列表，列表中是该列所有节点的(y, 值)。我们需要对每个列表排序：先按y升序，如果y相同则按节点值升序。排序后，提取节点值，形成该列的结果列表。

步骤5：按x顺序输出结果
将字典的所有键x取出，按从小到大的顺序排序。对于每个排序后的x，将步骤4中得到的该列节点值列表加入最终结果列表。

步骤6：边界情况考虑

• 树为空时，返回空列表。
• 所有节点值可能重复，但排序时值相等的情况顺序可任意（或保持稳定，但题目通常指定按值排序，所以相等时顺序不重要）。

步骤7：复杂度分析

• 时间复杂度：遍历树O(N)，其中N是节点数。排序开销：假设有C列，每列平均有N/C个节点，对每列排序总复杂度可接近O(N log N)（当树比较平衡时，列数与√N相关，但最坏情况是链状树，列数可达N，每列1个节点，排序总复杂度O(N)）。但更精确地，我们可以认为收集后所有节点需要一次全局排序或分列排序，总体O(N log N)。
• 空间复杂度：O(N)存储字典和递归栈（若用DFS递归，最坏O(N)）。

实现示例（伪代码/思路）

def verticalTraversal(root):
    if not root:
        return []
    
    from collections import defaultdict
    # 字典：key=x, value=list of (y, value)
    column_table = defaultdict(list)
    
    def dfs(node, x, y):
        if not node:
            return
        column_table[x].append((y, node.val))
        dfs(node.left, x-1, y+1)
        dfs(node.right, x+1, y+1)
    
    dfs(root, 0, 0)
    
    # 获取所有x并排序
    sorted_x = sorted(column_table.keys())
    result = []
    for x in sorted_x:
        # 对该列列表先按y排序，y相同按值排序
        column_table[x].sort(key=lambda item: (item[0], item[1]))
        # 提取值
        column_values = [val for (y, val) in column_table[x]]
        result.append(column_values)
    
    return result

总结
垂直遍历的核心是给每个节点分配坐标，按列分组，组内按行和值排序，最后按列顺序输出。通过DFS/BFS遍历一次树，并用哈希表分组，即可高效解决。注意排序规则可能因题目要求略有不同（例如有时只要求按从上到下顺序，不按值排序），但基本框架一致。