分布式移动网站开发技术,兰州网站定制公司,搞钱的路子网站,如何扫描一个网站的漏洞给定二叉树#xff0c;按垂序遍历返回其结点值。 对位于 (X, Y) 的每个结点而言#xff0c;其左右子结点分别位于 (X-1, Y-1) 和 (X1, Y-1)。 把一条垂线从 X -infinity 移动到 X infinity #xff0c;每当该垂线与结点接触时#xff0c;我们按从上到下的顺序报告结点的值… 给定二叉树按垂序遍历返回其结点值。 对位于 (X, Y) 的每个结点而言其左右子结点分别位于 (X-1, Y-1) 和 (X1, Y-1)。 把一条垂线从 X -infinity 移动到 X infinity 每当该垂线与结点接触时我们按从上到下的顺序报告结点的值 Y 坐标递减。 如果两个结点位置相同则首先报告的结点值较小。 按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。 示例 1 输入[3,9,20,null,null,15,7] 输出[[9],[3,15],[20],[7]] 解释 在不丧失其普遍性的情况下我们可以假设根结点位于 (0, 0) 然后值为 9 的结点出现在 (-1, -1) 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2) 值为 20 的结点出现在 (1, -1) 值为 7 的结点出现在 (2, -2)。 示例 2 输入[1,2,3,4,5,6,7] 输出[[4],[2],[1,5,6],[3],[7]] 解释 根据给定的方案值为 5 和 6 的两个结点出现在同一位置。 然而在报告 [1,5,6] 中结点值 5 排在前面因为 5 小于 6。 提示 树的结点数介于 1 和 1000 之间。 每个结点值介于 0 和 1000 之间。 来源力扣LeetCode 链接https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解法 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:vectorvectorint verticalTraversal(TreeNode* root) {mapint, vectorint m; queuepairint, TreeNode* q; q.push(make_pair(0, root)); while (!q.empty()){setpairint, int tmp; int len q.size();for (int i 0; i len; i){auto p q.front(); q.pop();tmp.insert(make_pair(p.first, p.second-val));if (p.second-left) q.push(make_pair(p.first - 1, p.second-left));if (p.second-right) q.push(make_pair(p.first 1, p.second-right));}for (auto p : tmp) m[p.first].push_back(p.second);}vectorvectorint res;for (auto kv : m) res.push_back(kv.second);return res;}
};
