LeetCode 题解工作台
二叉树的垂序遍历
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 二分·树·traversal
答案摘要
我们设计一个函数 $dfs(root, i, j)$，其中 和 表示当前节点的行和列。我们可以通过深度优先搜索的方式，将节点的行和列信息记录下来，存储在一个数组或列表 中，然后对 按照列、行、值的顺序进行排序。 接着，我们遍历 ，将相同列的节点值放到同一个列表中，最后返回这些列表。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。
对位于 (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 = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列 0 ：结点 1 、5 和 6 都在此列中。
1 在上面，所以它出现在前面。
5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列 1 ：只有结点 3 在此列中。
列 2 ：只有结点 7 在此列中。
示例 3：
输入：root = [1,2,3,4,6,5,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。 因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。
提示：
- 树中结点数目总数在范围
[1, 1000]内 0 <= Node.val <= 1000
解题思路
方法一：DFS + 排序
我们设计一个函数 ，其中 和 表示当前节点的行和列。我们可以通过深度优先搜索的方式，将节点的行和列信息记录下来，存储在一个数组或列表 中，然后对 按照列、行、值的顺序进行排序。
接着，我们遍历 ，将相同列的节点值放到同一个列表中，最后返回这些列表。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
def dfs(root: Optional[TreeNode], i: int, j: int):
if root is None:
return
nodes.append((j, i, root.val))
dfs(root.left, i + 1, j - 1)
dfs(root.right, i + 1, j + 1)
nodes = []
dfs(root, 0, 0)
nodes.sort()
ans = []
prev = -2000
for j, _, val in nodes:
if prev != j:
ans.append([])
prev = j
ans[-1].append(val)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Evaluate the candidate's ability to apply tree traversal algorithms like BFS and DFS.
- question_mark
Look for understanding of hash table usage for vertical column grouping.
- question_mark
Assess how the candidate handles sorting operations within the columns.
常见陷阱
外企场景- error
Confusing node positioning, such as incorrectly calculating the column and row positions.
- error
Failure to account for sorting nodes within the same column and row based on their values.
- error
Inefficient use of data structures, leading to unnecessary complexity.
进阶变体
外企场景- arrow_right_alt
What if the tree has only one node? The output should still be a list containing a single node in its own column.
- arrow_right_alt
Can we optimize for larger trees? Consider methods that reduce sorting overhead for large datasets.
- arrow_right_alt
How would the solution change if nodes were added dynamically, requiring frequent updates to the tree structure?