Hard
题目描述
给你二叉树的根结点 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
解题思路
这是一道综合性较强的树遍历问题，需要同时考虑位置坐标和排序规则。
核心思路：
- 首先需要为每个节点确定坐标位置
(row, col)，其中根节点位于(0, 0) - 左子节点的坐标为
(row + 1, col - 1)，右子节点为(row + 1, col + 1) - 收集所有节点的坐标和值信息
- 按照题目要求的优先级进行排序：列索引 → 行索引 → 节点值
- 将相同列的节点分组输出
解法分析：
- DFS遍历法：使用深度优先搜索遍历整棵树，记录每个节点的位置信息
- BFS遍历法：使用广度优先搜索，逐层处理节点
两种方法的时间复杂度相同，这里推荐使用 DFS 方法，代码更简洁。
排序策略： 对收集到的节点信息按以下优先级排序：
- 首先按列索引（col）升序
- 其次按行索引（row）升序
- 最后按节点值（val）升序
排序完成后，相同列的节点自然会按照从上到下、值从小到大的顺序排列，最后分组输出即可。
代码实现
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
vector<tuple<int, int, int>> nodes; // (col, row, val)
function<void(TreeNode*, int, int)> dfs = [&](TreeNode* node, int row, int col) {
if (!node) return;
nodes.push_back({col, row, node->val});
dfs(node->left, row + 1, col - 1);
dfs(node->right, row + 1, col + 1);
};
dfs(root, 0, 0);
sort(nodes.begin(), nodes.end());
vector<vector<int>> result;
int lastCol = INT_MIN;
for (auto [col, row, val] : nodes) {
if (col != lastCol) {
result.push_back({});
lastCol = col;
}
result.back().push_back(val);
}
return result;
}
};
class Solution:
def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
nodes = []
def dfs(node, row, col):
if not node:
return
nodes.append((col, row, node.val))
dfs(node.left, row + 1, col - 1)
dfs(node.right, row + 1, col + 1)
dfs(root, 0, 0)
nodes.sort()
result = []
last_col = float('-inf')
for col, row, val in nodes:
if col != last_col:
result.append([])
last_col = col
result[-1].append(val)
return result
public class Solution {
public IList<IList<int>> VerticalTraversal(TreeNode root) {
var nodes = new List<(int col, int row, int val)>();
void DFS(TreeNode node, int row, int col) {
if (node == null) return;
nodes.Add((col, row, node.val));
DFS(node.left, row + 1, col - 1);
DFS(node.right, row + 1, col + 1);
}
DFS(root, 0, 0);
nodes.Sort();
var result = new List<IList<int>>();
int lastCol = int.MinValue;
foreach (var (col, row, val) in nodes) {
if (col != lastCol) {
result.Add(new List<int>());
lastCol = col;
}
result[result.Count - 1].Add(val);
}
return result;
}
}
var verticalTraversal = function(root) {
const nodes = [];
function dfs(node, row, col) {
if (!node) return;
nodes.push([col, row, node.val]);
dfs(node.left, row + 1, col - 1);
dfs(node.right, row + 1, col + 1);
}
dfs(root, 0, 0);
nodes.sort((a, b) => {
if (a[0] !== b[0]) return a[0] - b[0];
if (a[1] !== b[1]) return a[1] - b[1];
return a[2] - b[2];
});
const result = [];
let lastCol = -Infinity;
for (const [col, row, val] of nodes) {
if (col !== lastCol) {
result.push([]);
lastCol = col;
}
result[result.length - 1].push(val);
}
return result;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | 其中 n 是节点数量。遍历所有节点需要 O(n)，排序需要 O(n log n) |
| 空间复杂度 | O(n) | 存储所有节点信息需要 O(n) 空间，递归栈深度最多为 O(h)，其中 h 是树的高度 |