2 minute read

Strive not to be a success, but rather to be of value. - Albert Einstein

从取经到代码：如何在大厂面试中攻克 Binary Tree Vertical Order Traversal

“取经的价值不只是拿到真经，而是一路上的思考、试错与修炼。”

准备 大厂 的 Principal/Senior Developer 面试时，刷题只是表层功夫，更重要的是如何展示你的思维方式。今天我们以一道常见的题目——Binary Tree Vertical Order Traversal——为例，来深入拆解不仅是解法本身，更是面试过程中如何推理、选择和表达的过程。

题目解读：不要急着上手敲代码

题意 给定一棵二叉树，把它的节点按照“垂直列”分组输出。根节点的列号是 0，左子树列号 −1，右子树列号 +1。输出结果需要从最左列到最右列依次排列，每列内部按 从上到下 的顺序，如果同一层次有多个节点，则按 从左到右 排列。

如何正确解读？ 在面试场景中，第一步是确认约束条件和输出要求，而不是急着说“哦，这是 BFS 题”。可以先和面试官确认：

  • 树的规模（通常 ≤ 10⁴ 节点，足够大但不会超内存）。
  • 是否需要处理值相同的情况（是的，节点值可能重复）。
  • 输出要求：是 LeetCode 314（只按列和层顺序），还是 LeetCode 987（还要考虑数值排序）。

面试亮点：资深候选人会主动澄清题目变体，这显示了系统思维和风险控制。

启发式思维：该走哪条路？

在算法面试中，常见的误区是直接跳到某个“熟悉的套路”（比如动态规划），结果方向错了。更好的方式是用启发式来判断。

对于本题，我们可以问自己几个关键问题：

  1. 需要全局最优还是局部顺序？ → 只是顺序遍历，不涉及最优子结构，因此不适合 DP。
  2. 需要逐层有序吗？ → 需要保证自上而下、同层左到右 → BFS 比 DFS 更自然。
  3. 需要额外排序吗？ → 如果只是 LeetCode 314，则只要保证 BFS 顺序即可，不需要全局排序。 → 如果是 987，则需要收集 (row, col, val) 并排序。

经验法则：如果题目强调 顺序输出，往往优先考虑 BFS；如果题目强调 路径最优/状态转移，才考虑 DP。

从哪里开始：构建思维支点

在拿到题目时，我通常会先画一个简单的例子：

       1
      / \
     2   3
    /     \
   4       5
  • 根节点 1 在列 0
  • 2 在列 −1, 3 在列 +1
  • 4 在列 −2, 5 在列 +2

输出应该是：[[4], [2], [1], [3], [5]]

通过这种例子，我们能快速验证思路：

  • 列号变化是否正确？
  • 遍历顺序是否符合题意？
  • 边界情况（左子树比右子树更深）是否覆盖？

这就是“checkpointing”思维：每走一步就给自己打断点，验证方向是否正确，而不是一口气写完代码最后才发现跑偏。

正确的方向：BFS + 哈希表

思路

  • 用一个 queue（广度优先队列）存储 (node, column)。
  • 用一个 dict/defaultdict(list) 存储列号 → 节点值。
  • 追踪最小列号和最大列号，最后按区间输出即可。

Python 实现

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

class TreeNode:
    def __init__(self, val: int = 0,
                 left: 'Optional[TreeNode]' = None,
                 right: 'Optional[TreeNode]' = None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        col_map = defaultdict(list)
        queue = deque([(root, 0)])

        min_col, max_col = 0, 0

        while queue:
            node, col = queue.popleft()
            col_map[col].append(node.val)

            min_col = min(min_col, col)
            max_col = max(max_col, col)

            if node.left:
                queue.append((node.left, col - 1))
            if node.right:
                queue.append((node.right, col + 1))

        return [col_map[c] for c in range(min_col, max_col + 1)]

代码细节剖析：别忽略”小问题”

Let’s drill down: 深入技术细节

在面试中，能够解释代码背后的机制往往比写出代码更重要。让我们深入分析两个关键细节：

1. 为什么 'Optional[TreeNode]' 需要引号？

class TreeNode:
    def __init__(self, val: int = 0, 
                 left: 'Optional[TreeNode]' = None, 
                 right: 'Optional[TreeNode]' = None):

核心问题：Optional[TreeNode] 表示”要么是 TreeNode 对象，要么是 None”，但在类定义内部，TreeNode 还没有完全定义完成。

技术原理：

  • 如果直接引用 TreeNode，Python 解释器会报错，因为它还不知道 TreeNode 是什么
  • Forward Reference（前向引用）：通过引号 'Optional[TreeNode]' 将类型注解包装成字符串
  • Python 的类型系统会在稍后解析这个字符串引用

版本演进：

  • 📌 Python 3.7+：必须使用引号的方式
  • 📌 Python 3.9+：可以使用更优雅的方式： 
    from __future__ import annotations  # 自动解析前向引用
  
class TreeNode:
    def __init__(self, val: int = 0, 
                 left: Optional[TreeNode] = None,  # 无需引号
                 right: Optional[TreeNode] = None):

面试要点：引号只是前向引用的技巧，与运行时无关，纯粹是为了类型检查。

2. 为什么 defaultdict(list) 用小写 list？

col_map = defaultdict(list)

核心概念：defaultdict 需要一个 可调用的工厂函数，当访问不存在的 key 时自动创建默认值。

技术细节：

  • list（小写）是 Python 的内建类，同时也是构造函数
  • list() 调用会创建空列表 []
  • 当执行 col_map[5].append(42) 且 col_map[5] 不存在时：
    1. defaultdict 自动调用 list() → 创建 []
    2. 将 [] 赋值给 col_map[5]
    3. 然后执行 append(42)
    4. 最终结果：{5: [42]}

常见误区：为什么不用 List（大写 L）？

  • List 来自 typing 模块，仅用于类型提示（如 List[int]）
  • List 在运行时不可调用，defaultdict(List) 会抛出错误
  • 类型提示 vs 运行时构造函数是两个不同的概念

实际演示：

from collections import defaultdict
from typing import List

# ✅ 正确：list 是可调用的构造函数
col_map = defaultdict(list)
col_map[1].append(42)  # 自动创建空列表并添加元素

# ❌ 错误：List 不是构造函数
# col_map = defaultdict(List)  # TypeError!

✨ 技术总结

概念 用途 关键点
'Optional[TreeNode]' 前向引用 类定义时 TreeNode 尚未完成，需要字符串包装
list (小写) 运行时构造函数 实际创建空列表的可调用对象
List (大写) 类型提示 仅用于静态类型检查，运行时不可调用

这些细节在面试中常被忽略，但一个 Principal 级别的开发者应该主动提及。这不仅展示了你写代码的熟练度，也展示了你对 Python 类型系统和语言底层机制 的深度理解。

拓展思考：DFS + 全局排序

如果面试官突然问：“那如果我要求同一列的节点要按值排序呢？” 此时 BFS 不够了。更好的做法是：

  • 用 DFS 收集所有节点 (row, col, val)。
  • 最后用 Python 的排序函数按 (col, row, val) 排序。
  • 时间复杂度 O(N log N)。

这显示了你对 问题变体的敏感度，以及在面试中不会被轻易打乱。

从取经到修炼：面试中的思维训练

解题就像取经，最终的真经并不只是结果，而是过程：

  • 先解读题目（确认需求，不盲目假设）。
  • 用启发式判断方向（是 BFS、DFS 还是 DP）。
  • 在小例子上 checkpoint 验证思路。
  • 在代码实现中关注语言细节。
  • 在交流中体现对变体、复杂度和可扩展性的思考。

就像乔布斯说的：“你不能只问用户要什么，而要理解他们真正需要的是什么。” 面试官也一样，不只是想看你写出代码，而是要看到你 思考问题、推理选择、权衡取舍 的能力。

总结

Binary Tree Vertical Order Traversal 本身并不是最难的题，但它提供了一个很好的机会去展示：

  • 你如何读题、澄清边界；
  • 你如何利用启发式快速确定方向；
  • 你如何在实现中关注细节与可扩展性；
  • 你如何在交流中展现深度与远见。

在 Principal 级别的面试中，写对代码只是敲门砖，真正的区分点在于 过程的思维展示。 记住：你不是去 recite（背公式），而是去 interpret（解释现象）、analyze（剖析问题）、decide（做出选择）。

✍️ 作者注：这篇文章基于我对 Binary Tree Vertical Order Traversal 的拆解，结合了算法、语言机制和面试策略。如果你也在取经路上，希望这篇文章能帮你走得更稳、更快。

Updated:

You may also enjoy

3 minute read