题目重点：按左到右列、上到下行输出二叉树，用BFS保留同坐标的左右遍历次序。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练根column0，左col−1、右col+1；同列按层上到下，同层同列按BFS左先顺序。不是同坐标再按value排序的另一Vertical Traversal合同。
解题路线
- queue存(node,col)，BFS出队把value追加到columns[col]，孩子按left/right入队。BFS天然保证行升序，同层顺序由左先入队确定。
- 记录minimum/maximum col，树的可达列连续，从min到max输出，无需把所有node三元组全排序。每条路径列每次±1，极值间的列必已经过。
- 若用DFS直接append，即使先左后右也可能把更深左节点写在同列浅右节点前，破坏top-down。DFS需要额外记录row并排序，不能与简单BFS等价。
- 同row/col不按数值重新排。若面试要求值排序，需加入row/value tie排序，明确它是不同输出规则。
手动走一遍
根0，左1的右子9与右2的左子3都在column0,row2；本训练中列0输出[0,9,3]，按value的变体输出[0,3,9]。两个答案不能随意互换。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import defaultdict,deque
def vertical_order(root):
"""Left-to-right columns; top-down rows; same position BFS left-before-right.
Not the variant sorting equal row/column by node value.
"""
if root is None:return []
columns=defaultdict(list);queue=deque([(root,0)]);minimum=maximum=0
while queue:
node,col=queue.popleft();columns[col].append(node.value)
minimum=min(minimum,col);maximum=max(maximum,col)
if node.left is not None:queue.append((node.left,col-1))
if node.right is not None:queue.append((node.right,col+1))
return [columns[col] for col in range(minimum,maximum+1)]
复杂度
O(N)时间，columns与queue合计O(N)空间，输出O(N)。min到max列宽≤N，遍历空列范围不超过节点规模。若要求row/value排序，复杂度可能O(N log N)。
易错点与追问
容易失分的边界
- DFS append没有排序会违反上到下。
- 同位置按value排序却题面要求出现顺序，会改变预期结果。
继续深挖
- 如果输出每列连同row坐标，接口应怎样扩展而不重新遍历？
- N叉树垂直列位置没有自然左右±1定义，必须先问布局规则。
