具体思路： 【LeetCode刷题记录|LeetCode 987. 二叉树的垂序遍历】和之前一道题思路相同；
具体思路：
/**
* 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:
vector> verticalTraversal(TreeNode* root) {
vector> ret;
if(!root)
return ret;
queue> q;
map>mp;
q.push({root,0});
while(!q.empty()){
int size=q.size();
map>temp;
while(size!=0){
size--;
auto pa=q.front();
q.pop();
temp[pa.second].push_back(pa.first->val);
if(pa.first->left){
q.push({pa.first->left,pa.second-1});
}
if(pa.first->right){
q.push({pa.first->right,pa.second+1});
}
}
for(auto it=temp.begin();
it!=temp.end();
it++){
sort(it->second.begin(),it->second.end());
mp[it->first].insert(mp[it->first].end(),it->second.begin(),it->second.end());
}
}
for(auto it=mp.begin();
it!=mp.end();
it++){
//sort(it->second.begin(),it->second.end());
ret.push_back(it->second);
}
return ret;
}
};
推荐阅读
- LeetCode|LeetCode刷题笔记（279.完全平方数）
- 算法|回溯算法——洛谷p1036
- 数据结构设计简单 LeetCode1656. 设计有序流
- leetcode|leetcode 数据库练习
- leetcode|LeetCode 5955. 摘水果 题目解析
- 算法刷题|LeetCode刷题笔记-21.合并两个有序链表
- LeetCode|LeetCode1143. 最长公共子序列
- #|力扣-105题 从前序与中序遍历序列构造二叉树（C++）- dfs
- 栈和队列|150. 逆波兰表达式求值