题目描述

/
* 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:
int Sum(TreeNode root,int depth)
{
if(!root) return 0;
if(!root->left &&!root->right ) return depth * root->val;
return Sum(root->left,depth+1)+Sum(root->right,depth+1);
}

int pathSum(TreeNode* root) {
    return Sum(root,0);
}

};

样例

int main() { scanf("%d%d", &n, &k); // 读入序列长度 n 和滑窗大小 k for (int i = 0; i < n; i++) scanf("%d", &a[i]); // 读入序列数据 // 寻找每个滑窗的最大值 int hh = 0, tt = -1; // 初始化队头和队尾指针 for (int i = 0; i < n; i++) { // 判断队头是否已滑出窗口 if (hh <= tt && i - k + 1 > q[hh]) hh++; // 维护队列，保证队首始终是最优值 while (hh <= tt && a[q[tt]] >= a[i]) tt--; q[++tt] = i; // 输出当前滑窗的最大值 if (i >= k - 1) printf("%d ", a[q[hh]]); } puts(""); // 换行 // 寻找每个滑窗的最小值 hh = 0, tt = -1; // 重置队头和队尾指针 for (int i = 0; i < n; i++) { // 判断队头是否已滑出窗口 if (hh <= tt && i - k + 1 > q[hh]) hh++; // 维护队列，保证队首始终是最优值 while (hh <= tt && a[q[tt]] <= a[i]) tt--; q[++tt] = i; // 输出当前滑窗的最小值 if (i >= k - 1) printf("%d ", a[q[hh]]); } puts(""); return 0; }

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla