题目
给你二叉树的根结点 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
解答
解题思路如下：
- 编写了一个辅助函数
verticalTraversalHelper，用于递归处理二叉树。该函数的参数包括当前结点root、当前结点所在的列数x、当前结点所在的行数y，以及一个用于存储结点值的map结构nodes。在该函数中，首先判断当前结点是否为空，若为空则直接返回；否则，将当前结点的值添加到nodes结构中对应的列和行中，并递归调用该函数处理左右子树，列数x根据左右移动。 - 定义了主函数
verticalTraversal，用于实现按照列的顺序遍历二叉树。在该函数中，首先定义了一个二维数组result，用于存储最终结果。然后判断根结点是否为空，若为空则直接返回空数组。接下来使用map结构nodes来存储每一列的结点值，其中 key 为列数，value 为行数和结点值的映射。 - 调用辅助函数
verticalTraversalHelper处理二叉树，将结点按照列的顺序分组，存储在nodes结构中。 - 使用队列
columns对列数进行排序，然后按照列数从小到大遍历结点值，并将其添加到结果数组result中。在遍历过程中，首先从队列中取出一个列数col，然后使用优先队列pq对该列的行数和结点值进行排序。将当前列的结点值按照行数加入优先队列。 - 将优先队列中的结点值按照行数顺序取出，存储在一个临时数组
colValues中。 - 将
colValues数组添加到结果数组result中。 - 最后返回结果数组
result。 - 在
main函数中，创建了一个测试二叉树，并调用verticalTraversal函数进行遍历，然后打印结果。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 辅助函数，用于将二叉树的结点按照列的顺序进行分组
void verticalTraversalHelper(TreeNode *root, int x, int y, map<int, map<int, vector<int>>> &nodes) {
if (!root)
return;
// 在对应的列和行中添加当前结点的值
nodes[x][y].push_back(root->val);
// 递归处理左子树和右子树，列数x根据左右移动
verticalTraversalHelper(root->left, x - 1, y + 1, nodes);
verticalTraversalHelper(root->right, x + 1, y + 1, nodes);
}
// 主函数，返回按照列的顺序遍历的结点值的二维数组
vector<vector<int>> verticalTraversal(TreeNode *root) {
// 存储结点值的二维数组
vector<vector<int>> result;
// 如果根结点为空，直接返回空数组
if (!root)
return result;
// 使用map来存储每一列的结点值，key为列数，value为行数和结点值的映射
map<int, map<int, vector<int>>> nodes;
// 递归处理二叉树，将结点按照列的顺序分组
verticalTraversalHelper(root, 0, 0, nodes);
// 使用队列对列数进行排序
queue<int> columns;
for (auto &node : nodes)
columns.push(node.first);
// 按照列数从小到大遍历结点值，并添加到结果数组中
while (!columns.empty()) {
int col = columns.front();
columns.pop();
// 使用优先队列对行数和结点值进行排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
// 将当前列的结点值按照行数加入优先队列
for (auto &node : nodes[col]) {
int row = node.first;
for (int val : node.second) {
pq.push({row, val});
}
}
// 将当前列的结点值按照行数顺序添加到结果数组中
vector<int> colValues;
while (!pq.empty()) {
colValues.push_back(pq.top().second);
pq.pop();
}
result.push_back(colValues);
}
return result;
}
};