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

1. 问题描述

给定一棵二叉树的根节点 root，要求按照"垂直顺序"遍历这棵树，并返回其结点值的列表。所谓"垂直顺序"是指：

• 如果两个结点位于同一行（即相同深度）和同一列（即相同水平位置），则应按照结点值从小到大排序。
• 整个遍历结果应按列从左到右、同一列内按行从上到下（若行相同则按结点值排序）的顺序返回。

示例：
考虑以下二叉树：

       3
      / \
     9   20
        /  \
       15   7

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

• 结点 9 的列为 -1。
• 结点 3 的列为 0。
• 结点 15 和 20 的列均为 1（但 15 深度为 2，20 深度为 1，所以 20 在前）。
• 结点 7 的列为 2。

2. 关键概念与思路

垂直遍历的核心在于为每个结点分配一个"坐标"（列，行，值），然后按特定规则收集这些坐标对应的结点值。

• 列（Column）：根节点的列设为 0。如果某个结点列号为 col，则其左子结点的列号为 col - 1，右子结点的列号为 col + 1。
• 行（Row）：即结点的深度。根节点的深度为 0，每向下一层深度加 1。
• 排序规则：首先按列从小到大排序；对于同一列，按行从小到大排序；如果行也相同，则按结点值从小到大排序。

3. 解题步骤（基于广度优先搜索BFS）

步骤1：初始化数据结构

• 使用一个队列进行 BFS，队列元素为 (node, row, col)。
• 使用一个字典（或哈希表） column_table，键为列号，值为一个列表，存储该列的所有 (row, value) 对。

步骤2：BFS遍历二叉树

• 将根节点 (root, 0, 0) 入队。
• 当队列不为空时，出队一个元素 (node, row, col)。
• 将 (row, node.val) 添加到 column_table[col] 对应的列表中。
• 如果存在左子结点，将 (node.left, row + 1, col - 1) 入队。
• 如果存在右子结点，将 (node.right, row + 1, col + 1) 入队。

步骤3：整理结果

• 获取 column_table 中所有列号，并按升序排序。
• 对于每一列，获取其 (row, value) 列表，并按照以下规则排序：
  1. 首先按 row 升序排序。
  2. 如果 row 相同，则按 value 升序排序。
• 排序后，提取每个 value 并按顺序放入该列对应的结果子列表中。
• 将所有列的结果子列表按列顺序组合成最终列表。

4. 复杂度分析

• 时间复杂度：O(N log N)，其中 N 为结点数。BFS 遍历每个结点一次 O(N)，排序操作可能需 O(N log N)（如每列内排序）。
• 空间复杂度：O(N)，用于存储队列、字典和结果。

5. 代码实现（Python示例）

from collections import deque, defaultdict
from typing import List, Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def verticalTraversal(root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    
    # column_table 的键为列号，值为 (row, value) 的列表
    column_table = defaultdict(list)
    
    # BFS 队列：元素为 (node, row, col)
    queue = deque([(root, 0, 0)])
    
    while queue:
        node, row, col = queue.popleft()
        
        # 记录当前结点的行和值到对应列
        column_table[col].append((row, node.val))
        
        # 处理左子结点
        if node.left:
            queue.append((node.left, row + 1, col - 1))
        # 处理右子结点
        if node.right:
            queue.append((node.right, row + 1, col + 1))
    
    # 获取所有列号并排序
    sorted_columns = sorted(column_table.keys())
    
    # 构建结果
    result = []
    for col in sorted_columns:
        # 对当前列的所有 (row, value) 排序：先按 row，再按 value
        column_table[col].sort(key=lambda x: (x[0], x[1]))
        # 提取排序后的值
        sorted_values = [val for row, val in column_table[col]]
        result.append(sorted_values)
    
    return result

6. 示例运行过程
以示例二叉树 [3,9,20,null,null,15,7] 为例：

• 初始：队列 [(3,0,0)]。
• 处理结点 3：列 0 记录 [(0,3)]；左子结点 9 入队 (9,1,-1)；右子结点 20 入队 (20,1,1)。
• 处理结点 9：列 -1 记录 [(1,9)]；无子结点。
• 处理结点 20：列 1 记录 [(1,20)]；左子结点 15 入队 (15,2,0)；右子结点 7 入队 (7,2,2)。
• 处理结点 15：列 0 记录增加为 [(0,3), (2,15)]。
• 处理结点 7：列 2 记录 [(2,7)]。
• 排序：列排序为 [-1, 0, 1, 2]；每列内排序后值分别为 [9], [3,15], [20], [7]。
• 最终结果：[[9], [3,15], [20], [7]]。

7. 注意事项

• 若使用深度优先搜索（DFS），也需记录行列信息，但需注意遍历顺序可能影响同一行列内的排序，故最后仍需排序。
• 若要求同一列内只按行排序（不按值排序），则排序条件可简化为仅按 row 排序。
• 此方法适用于任意二叉树，包括非完全二叉树。