搜索+哈希/平衡树，LeetCode 987. 二叉树的垂序遍历
目录
一、题目
1、题目描述
2、接口描述
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
给你二叉树的根结点
root，请你设计算法计算二叉树的 垂序遍历 序列。对位于
(row, col)的每个结点而言，其左右子结点分别位于(row + 1, col - 1)和(row + 1, col + 1)。树的根结点位于(0, 0)。二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
返回二叉树的 垂序遍历 序列。
2、接口描述
/*** 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<vector<int>> verticalTraversal(TreeNode* root) {}
};3、原题链接
987. 二叉树的垂序遍历
二、解题报告
1、思路分析
我们由父节点的坐标可以推出左右孩子的坐标，那么我们可以从根节点进行广搜或者深搜，推出所有节点的坐标，然后对每一列按照行坐标和节点值进行排序，记录返回值即可
思路很简单，就是一模拟题，代码或许还可以写的更优雅。
2、复杂度
时间复杂度： O(nlogn)空间复杂度：O(n)
3、代码详解
/*** 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:
#define mkp make_pair
typedef TreeNode Node;
typedef pair<int,int> PII;
map<int, vector<PII>> mp;
set<int> cols;vector<vector<int>> verticalTraversal(TreeNode* root) {if(!root) return {};mp.clear(), cols.clear();function<void(Node*, const PII&)> dfs = [&](Node* x, const PII& p){mp[p.second].emplace_back(mkp(p.first, x->val));cols.insert(p.second);if(x->left) dfs(x->left, mkp(p.first+1, p.second-1));if(x->right) dfs(x->right, mkp(p.first+1, p.second+1));};dfs(root, mkp(0, 0));vector<vector<int>> ret(cols.size());int tot = 0;for(auto x : cols){sort(mp[x].begin(), mp[x].end());for(auto& p : mp[x])ret[tot].emplace_back(p.second);tot++;}return ret;}
};