Amazon 树的纵向浏览：列坐标、层序与同位置顺序

题意与假设

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

• 可辨问点是树的纵向浏览，具体同行同列tie未说明。练习定义根列0、左−1右+1；列递增、列内由浅到深，同位置按左优先BFS顺序。
• 节点字段value/left/right，无环/共享身份。需要同行同列按数值排序的变体另加排序，不混到当前实现。

解题路线

1. 队列保存(node,column)，取节点时写columns[column]，然后左孩子列−1、右孩子列+1。BFS保证浅层先出队，同层左到右扩展使本练习tie稳定。
2. 维护min/max列，最后按连续列范围取结果。真正二叉树从根走到某列的过程中会经过中间列，因此没有需要填入不存在列的洞。
3. DFS按列直接append可能先输出左子树深层再输出右子树浅层，违反列内深度顺序；若用DFS就显式保存row/order再排序。
4. 独立测试按从根到节点的L/R路径求row/col和路径顺序，比较列分组，不只用另一份queue代码作参考。深链采用迭代以免递归栈限制。

手动走一遍

根1，左2右3，2右孩子4与3左孩子5都在列0深度2，练习输出列−1[2]、列0[1,4,5]、列1[3]。如果指定同位置按value排序，可改值使结果不同，不能用同一测试假装两合同一致。

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)]

复杂度

N节点O(N)时间、列结果O(N)，queue O(B)最大层宽；列范围宽≤N。若值排序变体每列按(row,value)，一般O(N log N)上界，当前代码未实现该合同。

易错点与追问

容易失分的边界

• 用DFS append而没有row排序。
• 以value当列坐标或节点身份。
• 不问tie却默认熟题数值排序。

继续深挖

• 如何在稳定BFS顺序与按value排序两变体间设计反例？
• 如果只返回每列最上方节点，何时可以提前停止？