DEV Community
·
二叉树的垂直遍历。314. 二叉树的垂直顺序遍历。
💡
原文约700字/词，阅读约需3分钟。
📝
内容提要
给定一个二叉树，使用广度优先搜索（BFS）按列垂直遍历，记录每个节点的列号，并通过哈希表存储列号与节点值的映射，最后转换为列表。时间复杂度为O(N)，空间复杂度为O(N)。
🎯
关键要点
- 给定一个二叉树，使用广度优先搜索按列垂直遍历。
- 在同一列中，元素应从上到下排列，且同一行的元素应从左到右排列。
- 使用哈希表存储列号与节点值的映射。
- 根节点的列号为0，左子节点列号为column - 1，右子节点列号为column + 1。
- 在遍历过程中，记录最小和最大列号，以便最终转换哈希表为列表。
- 时间复杂度为O(N)，空间复杂度为O(N)。
❓
延伸问答
如何实现二叉树的垂直遍历？
使用广度优先搜索（BFS）按列遍历，记录每个节点的列号，并通过哈希表存储列号与节点值的映射。
二叉树垂直遍历的时间和空间复杂度是多少？
时间复杂度为O(N)，空间复杂度为O(N)。
在垂直遍历中，如何处理同一列的节点顺序？
同一列中的元素应从上到下排列，且同一行的元素应从左到右排列。
如何计算当前节点的列号？
根节点的列号为0，左子节点列号为column - 1，右子节点列号为column + 1。
在遍历过程中如何记录列号的范围？
在遍历过程中，记录最小和最大列号，以便最终转换哈希表为列表。
如何将哈希表转换为最终的列表格式？
根据记录的最小和最大列号，遍历哈希表，将每个列的节点值列表添加到结果列表中。
➡️
