Bloomberg 二叉树纵向遍历：列、层与 BFS 并列顺序

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版 root 列 0，左子列−1、右子列+1；同列先按行数，再按 BFS 左到右的遇见顺序。
• 空树返回 []；若题目是 LC987 的同列同层按值排序，应改变并列规则，不可混用。

解题路线

1. 队列从 root 开始 BFS，节点附列号；弹出时追加到 columns[col]。
2. 先压 left 再 right；BFS 处理层数递增，因此每列列表天然按层数和同层左到右排序。
3. 最后按列号升序输出。若希望完全避免列排序，可扫描时记录 minCol/maxCol 并按范围取。
4. 用同列同层的两个节点专门测试稳定顺序，防误加值排序。

手动走一遍

root=3，左 9、右 8；9 的右子 4 与 8 的左子 0 都在列 0、层 2。BFS 左先入队，列 0 输出 [3,4,0]，而不是按值 [3,0,4]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import defaultdict, deque


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


def vertical_order(root):
    """Group by column; BFS preserves row and left-to-right tie order."""
    if root is None:
        return []
    columns = defaultdict(list)
    queue = deque([(root, 0)])
    while queue:
        node, column = queue.popleft()
        columns[column].append(node.value)
        if node.left is not None:
            queue.append((node.left, column - 1))
        if node.right is not None:
            queue.append((node.right, column + 1))
    return [columns[column] for column in sorted(columns)]

复杂度

N 节点遍历 O(N)，C 个不同列排序 O(C log C)，队列/列结果 O(N) 空间；列号在高度 H 范围内。

易错点与追问

容易失分的边界

• 把纵向遍历写成按值排序的另一道题。
• DFS 后未按层和遇见序整理。
• 先入右子造成同层并列顺序变化。
• 空树不处理。

继续深挖

• 若同列同层要按值排序？
• 若只要某一列？
• 树以流式边到达可否在线输出？