AcWing 1240. 完全二叉树的权值
原题链接
简单
作者:
王小强
,
2021-02-12 17:31:40
,
所有人可见
,
阅读 307
复习总结提高版
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1E5 + 1;
int n;
long s[N];
// 解法1 -- 数学法
// 所以说,满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满。
// 因此,这句话是对的。
signed main(int argc, char const *argv[]) {
scanf("%d", &n);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
s[i] = s[i - 1] + x;
}
int idx = 1, ans;
long max_s = -0x7fffffff;
while (idx <= n) {
long sum = s[min((idx << 1) - 1, n)] - s[idx - 1];
if (sum > max_s) {
max_s = sum;
ans = log2(idx) + 1;
}
idx <<= 1;
}
printf("%d\n", ans);
return 0;
}
感觉代码还是不够简捷,做了很多重复的计算!
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
using LL = long long;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {};
~TreeNode() {};
};
int n, x;
TreeNode* buildTree(vector<int>& nums) {
// corner case
if (nums.empty()) return nullptr;
auto root = new TreeNode(nums.front());
queue<TreeNode*> q{{root}};
int idx = 0;
while (not q.empty()) {
auto cur = q.front(); q.pop();
int left_idx = idx << 1 | 1;
int right_idx = (idx << 1) + 2;
if (left_idx >= n) break;
cur->left = new TreeNode(nums[left_idx]);
q.emplace(cur->left);
if (right_idx >= n) break;
cur->right = new TreeNode(nums[right_idx]);
q.emplace(cur->right);
++idx;
}
return root;
}
int levelOrder(TreeNode* root) {
queue<TreeNode*> q{{root}};
int level = 0, max_level = 0;
LL max_sum = LONG_MIN;
while (not q.empty()) {
++level;
LL sum = 0;
auto sz = q.size();
while (sz--) {
auto cur = q.front(); q.pop();
sum += cur->val;
if (cur->left) q.emplace(cur->left);
if (cur->right) q.emplace(cur->right);
}
if (sum > max_sum) {
max_sum = sum;
max_level = level;
}
}
return max_level;
}
int main(void) {
scanf("%d", &n);
vector<int> nums;
for (int i = 0; i < n; ++i) {
cin >> x;
nums.emplace_back(x);
}
cout << levelOrder(buildTree(nums)) << endl;
}