Day95 | 灵神 | 二叉树 二叉树的垂序遍历

Day95 | 灵神 | 二叉树 二叉树的垂序遍历

987.二叉树的垂序遍历

987. 二叉树的垂序遍历 - 力扣（LeetCode）

思路：

这道题是个hard题，emm感觉是个mid题

首先这道题难点不在递归，因为递归完成的任务只是标记每个节点的row和col而已

难在对数据的处理，其实也不难，就是把所有顶点的值记录到三元组里面

第一个元素col，第二个元素row，第三个元素节点的值，按照这三个元素排序就行

按照第一个元素大小排，一样的话看第二个，还一样的话看第三个，最后输出出来就行

完整代码：

笔者用的是map<int,vector<pair<int,int>>>

第一个元素大小的排序在插入map时已经完成，因为map底层是红黑树

那就只需要对col相同的vector<pair<int,int>>排序就好了，直接使用sort

sort排序pair就是先看第一个元素大小，一样的话看第二个元素

class Solution {
public:map<int,vector<pair<int,int>>> p;void tra(TreeNode *t,int row,int col){if(t==nullptr)return ;p[col].emplace_back(row,t->val);tra(t->left,row+1,col-1);tra(t->right,row+1,col+1);}vector<vector<int>> verticalTraversal(TreeNode* root) {tra(root,0,0);vector<vector<int>> res;for(auto c:p){//排列第二个第三个元素大小ranges::sort(c.second);vector<int> path;for(auto s:c.second)path.push_back(s.second);res.push_back(path);}return res;}
};

灵神代码（四个写法，我只贴了写法一）

class Solution {map<int, vector<pair<int, int>>> groups;void dfs(TreeNode *node, int row, int col) {if (node == nullptr) {return;}// col 相同的分到同一组groups[col].emplace_back(row, node->val);dfs(node->left, row + 1, col - 1);dfs(node->right, row + 1, col + 1);}public:vector<vector<int>> verticalTraversal(TreeNode *root) {dfs(root, 0, 0);vector<vector<int>> ans;for (auto &[_, g] : groups) {ranges::sort(g);vector<int> vals;for (auto &[_, val] : g) {vals.push_back(val);}ans.push_back(vals);}return ans;}
};