百度站长工具域名查询,外围网站做代理,wordpress破解版下载,牟长青 做网站推广的四个基本要点目录 一、题目
1、题目描述
2、接口描述
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解 一、题目
1、题目描述 给你二叉树的根结点 root #xff0c;请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言#xff0c;其左右子结…目录 一、题目
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:vectorvectorint 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 pairint,int PII;
mapint, vectorPII mp;
setint cols;vectorvectorint verticalTraversal(TreeNode* root) {if(!root) return {};mp.clear(), cols.clear();functionvoid(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.first1, p.second-1));if(x-right) dfs(x-right, mkp(p.first1, p.second1));};dfs(root, mkp(0, 0));vectorvectorint 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;}
};
