力扣9.2

199.二叉树的右视图

题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

数据范围

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

分析

树的层次遍历，每次返回那一层最边上的元素，可以使用两个deque实现

代码

/*** 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:deque<TreeNode*> tmp, ve;vector<int> res; void bfs(TreeNode* q) {ve.push_back(q);while(ve.size()) {tmp = ve;res.push_back(ve.back()->val);ve.clear();while(tmp.size()) {auto now = tmp.front();tmp.pop_front();auto l = now -> left, r = now -> right;if(l != nullptr) ve.push_back(l);if(r != nullptr) ve.push_back(r);}}}vector<int> rightSideView(TreeNode* root) {if(root == nullptr) return res;bfs(root);return res;}
};

---

637.二叉树的层平均值

题目

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

数据范围

• 树中节点数量在[1, 104] 范围内
• -2^31 <= Node.val <= 2^31 - 1

分析

使用两个vector实现树的层次遍历

代码

/*** 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<TreeNode*> tmp1, tmp2;vector<double> res;void bfs(TreeNode* p) {tmp2.push_back(p);while(tmp2.size()) {tmp1 = tmp2;tmp2.clear();double ave = 0;double cnt = 0;while(tmp1.size()) {auto now = tmp1.back();ave += now -> val;cnt += 1;tmp1.pop_back();auto l = now -> left, r = now -> right;if(l != nullptr) tmp2.push_back(l);if(r != nullptr) tmp2.push_back(r);}res.push_back(ave / cnt);}} vector<double> averageOfLevels(TreeNode* root) {bfs(root);return res;}
};

---

2110.股票平滑下跌阶段的数目

题目

给你一个整数数组 prices ，表示一支股票的历史每日股价，其中 prices[i] 是这支股票第 i 天的价格。

一个 平滑下降的阶段 定义为：对于 连续一天或者多天 ，每日股价都比 前一日股价恰好少 1 ，这个阶段第一天的股价没有限制。

请你返回 平滑下降阶段 的数目。

数据范围

• 1 <= prices.length <= 105
• 1 <= prices[i] <= 105

分析

对于price[i]，他对答案的贡献是他且在他前面的平滑下降的序列的长度，例如对于 8、7、4、3、2、1这样的序列，当遍历到1时，他的贡献为4321、321、21、1四个，因此只要找到当前数所在的平滑下降的序列，计算贡献加入答案即可

代码

class Solution {
public:long long getDescentPeriods(vector<int>& prices) {long long res = 0;long long cnt = 0;for(int i = 0; i < prices.size(); i ++ ) {if(i && prices[i] != prices[i - 1] - 1) {cnt = 0;}res += ++ cnt;}return res;}
};