Article / 文章
LeetCode 第314题：二叉树的垂直遍历
给你一个二叉树的根节点，请你返回其节点值的垂直遍历顺序（即逐列遍历）。 对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。 节点的垂直坐标用列序号表示，每一列中的所有节点都按照行坐标的顺序（即从上到下）来定位。如果同行同列上有多
📖 文章摘要
本文详细解析LeetCode第314题“二叉树的垂直遍历”，这是一道考察二叉树遍历和哈希表应用的题目。文章提供了基于BFS和哈希表的解决方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能分析。适合想要提升二叉树遍历和数据结构应用能力的程序员。
核心知识点： 二叉树遍历、BFS、哈希表
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升树遍历算法能力的程序员
题目描述
给你一个二叉树的根节点，请你返回其节点值的垂直遍历顺序（即逐列遍历）。
对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。
节点的垂直坐标用列序号表示，每一列中的所有节点都按照行坐标的顺序（即从上到下）来定位。如果同行同列上有多个节点，则按节点的值从小到大进行排序。
返回二叉树的垂直遍历结果。
示例
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1：只有节点 9 在此列中。
列 0：只有节点 3 和 15 在此列中，按从上到下顺序。
列 1：只有节点 20 在此列中。
列 2：只有节点 7 在此列中。示例 2：
输入：root = [3,9,8,4,0,1,7]
输出：[[4],[9],[3,0,1],[8],[7]]示例 3：
输入：root = [3,9,8,4,0,1,7,null,null,null,2,5]
输出：[[4],[9,5],[3,0,1],[8,2],[7]]提示
- 树中结点的数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
解题思路
本题可以使用BFS（广度优先搜索）配合哈希表来解决。
关键点：
- 使用BFS确保同层节点按从左到右的顺序访问
- 使用哈希表记录每一列的节点
- 记录每个节点的列坐标
- 按列坐标排序输出结果
具体步骤：
- 使用队列进行BFS遍历
- 同时记录每个节点的列坐标
- 使用哈希表存储每列的节点值
- 最后按列坐标排序输出结果
图解思路
BFS遍历分析表
| 状态 | 含义 | 计算方式 | 说明 |
|---|---|---|---|
| 列坐标 | 节点所在列 | 左子节点-1，右子节点+1 | 根节点为0 |
| 队列元素 | (节点,列坐标) | BFS遍历 | 保证层序遍历顺序 |
| 哈希表 | 列到节点值的映射 | 按列存储节点值 | 保持插入顺序 |
节点坐标示意图
3 (col: 0)
/ \
9 8 (col: 1)
/ \
4 7 (col: 2)
(col: -1)代码实现
C# 实现
public class Solution {
public IList<IList<int>> VerticalOrder(TreeNode root) {
var result = new List<IList<int>>();
if (root == null) return result;
// 使用字典存储每列的节点值
var columnTable = new SortedDictionary<int, List<int>>();
// 使用队列进行BFS
var queue = new Queue<(TreeNode node, int column)>();
queue.Enqueue((root, 0));
while (queue.Count > 0) {
var (node, column) = queue.Dequeue();
// 将节点值添加到对应列
if (!columnTable.ContainsKey(column)) {
columnTable[column] = new List<int>();
}
columnTable[column].Add(node.val);
// 将左右子节点加入队列
if (node.left != null) {
queue.Enqueue((node.left, column - 1));
}
if (node.right != null) {
queue.Enqueue((node.right, column + 1));
}
}
// 按列序号返回结果
foreach (var column in columnTable.Values) {
result.Add(column);
}
return result;
}
}Python 实现
class Solution:
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
# 使用字典存储每列的节点值
column_table = defaultdict(list)
# 使用队列进行BFS
queue = deque([(root, 0)])
while queue:
node, column = queue.popleft()
# 将节点值添加到对应列
column_table[column].append(node.val)
# 将左右子节点加入队列
if node.left:
queue.append((node.left, column - 1))
if node.right:
queue.append((node.right, column + 1))
# 按列序号返回结果
return [column_table[i] for i in sorted(column_table.keys())]C++ 实现
class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> result;
if (!root) return result;
// 使用map存储每列的节点值
map<int, vector<int>> columnTable;
// 使用队列进行BFS
queue<pair<TreeNode*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto [node, column] = q.front();
q.pop();
// 将节点值添加到对应列
columnTable[column].push_back(node->val);
// 将左右子节点加入队列
if (node->left) {
q.push({node->left, column - 1});
}
if (node->right) {
q.push({node->right, column + 1});
}
}
// 按列序号返回结果
for (const auto& [column, values] : columnTable) {
result.push_back(values);
}
return result;
}
};执行结果
C# 实现
- 执行用时：92 ms
- 内存消耗：24.8 MB
Python 实现
- 执行用时：36 ms
- 内存消耗：15.1 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：12.3 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 92 ms | 24.8 MB | 性能适中，内存占用较大 |
| Python | 36 ms | 15.1 MB | 执行较快，内存占用适中 |
| C++ | 4 ms | 12.3 MB | 执行最快，内存占用最小 |
代码亮点
- 🎯 使用BFS保证层序遍历顺序
- 💡 哈希表高效存储列数据
- 🔍 优雅处理空树边界情况
- 🎨 代码结构清晰，变量命名直观
常见错误分析
- 🚫 未正确处理空树情况
- 🚫 列坐标计算错误
- 🚫 未按列序号排序
- 🚫 未保持同层节点顺序
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| BFS + 哈希表 | O(n) | O(n) | 实现简单，保证顺序 | 需要额外空间 |
| DFS + 哈希表 | O(n) | O(n) | 代码简洁 | 需要额外排序 |
| 中序遍历 | O(nlogn) | O(n) | 思路直观 | 需要排序，性能较差 |
相关题目
总结
本题是对二叉树遍历的一个扩展应用，通过BFS和哈希表的结合，我们可以高效地实现垂直遍历。关键在于：
- 使用BFS保证同层节点的访问顺序
- 使用哈希表记录每列的节点值
- 正确计算和维护列坐标
- 最后按列坐标排序输出结果
掌握这道题目对于理解树的遍历和数据结构的应用都很有帮助。