力扣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;
    }
};