Swift 实现二叉树垂直遍历：LeetCode 314 完整解析与实战示例

摘要

在日常项目中，处理「树状结构」并不是稀罕事，比如做组织架构图、文件夹视图或者评论嵌套列表，我们经常会遇到对树的各种“奇怪”遍历方式。今天这题 LeetCode 314 —— Binary Tree Vertical Order Traversal（二叉树的垂直遍历），就考验了我们如何按垂直方向组织二叉树节点。

用 Swift 来解这题，既锻炼 BFS 的功底，也让我们更清晰地思考数据结构在空间维度上的组织方式。

描述

原题是这样说的：

给你一棵二叉树，要求按「垂直顺序」遍历这棵树，也就是从左到右，按每一列收集节点。如果同一列上有多个节点，则按从上到下的顺序排列。

举个例子：

输入：

    3
   / \
  9   8
 / \ / \
4  0 1  7

输出：

[
 [4],
 [9],
 [3, 0, 1],
 [8],
 [7]
]

我们可以看到，节点是按照“列”的方式被输出的，左边的列（值更小）先输出，垂直方向上再按从上往下排列。

题解答案

要按“列”的方式遍历二叉树，并且保证从上到下的顺序，首选 BFS（广度优先搜索）。因为 DFS 虽然也能遍历整棵树，但不容易保持“从上往下”的顺序。我们可以用一个队列来记录每个节点和它所在的“列索引”，然后逐层展开。

核心逻辑如下：

1. 给每个节点一个「列号」col，根节点为 0。
2. 左子节点的 col = 父节点 - 1，右子节点的 col = 父节点 + 1。
3. 用一个字典 colMap 存储每一列的节点。
4. 记录列的最小值和最大值，方便最后输出排序。

题解代码分析

import Foundation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func verticalOrder(_ root: TreeNode?) -> [[Int]] {
    guard let root = root else { return [] }

    var colMap: [Int: [Int]] = [:]     // 存储每列的节点值
    var queue: [(TreeNode, Int)] = [(root, 0)] // 节点和它对应的列索引
    var minCol = 0
    var maxCol = 0

    while !queue.isEmpty {
        let (node, col) = queue.removeFirst()

        colMap[col, default: []].append(node.val)
        minCol = min(minCol, col)
        maxCol = max(maxCol, col)

        if let left = node.left {
            queue.append((left, col - 1))
        }
        if let right = node.right {
            queue.append((right, col + 1))
        }
    }

    var result: [[Int]] = []
    for i in minCol...maxCol {
        result.append(colMap[i] ?? [])
    }
    return result
}

代码关键点解释：

• queue 使用 tuple (TreeNode, Int) 表示每个节点及其对应列。
• colMap 用字典把列号映射成一个数组，保存每列的值。
• BFS 确保了“从上到下”的顺序。
• 最后用 minCol...maxCol 依序提取每列结果，保证左到右。

示例测试及结果

我们写个 Demo 来验证一下这个函数是不是按预期工作：

// 构造树：
//     3
//    / \
//   9   8
//  / \ / \
// 4  0 1  7

let root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(8)
root.left?.left = TreeNode(4)
root.left?.right = TreeNode(0)
root.right?.left = TreeNode(1)
root.right?.right = TreeNode(7)

let result = verticalOrder(root)
print(result)
// 输出：[[4], [9], [3, 0, 1], [8], [7]]

解释一下输出：

• 列 -2：只有 4
• 列 -1：只有 9
• 列 0：3, 0, 1（从上到下）
• 列 1：8
• 列 2：7

顺序和题目要求完全一致

时间复杂度

• 每个节点只会遍历一次，所以时间复杂度是 O(n)，其中 n 是二叉树的节点数量。
• 字典和队列的操作都是常数时间内完成的。

空间复杂度

• 队列最多同时保存一层节点，最坏情况下是满二叉树的一层，复杂度是 O(n)。
• 额外的 colMap 字典也要保存所有节点，所以整体空间复杂度也是 O(n)。

总结

这题不只是一次 BFS 的考察，更是对“空间索引”的思考方式的一种锻炼：

• 如果你在做一个需要按“列”展示数据的系统，比如：楼层展示、评论层级分区、地图格子渲染，那这题的建模方式就很有参考意义。
• Swift 写 BFS 很直观，但队列用数组操作 removeFirst() 时注意性能（如果性能敏感可以用双端队列）。
• 最终输出要注意列的排序顺序，维护好 minCol 和 maxCol 是一个非常实用的小技巧。