数组二叉树
标题：数组二叉树 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2*N和2*N+1，并且我们用值-1代表一个节点为空。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Main {
public:
vector<int> getRes(vector<int> vec) {
vector<int> res;
int len = vec.size();
int minPos = 0;
for (int i = 1; i < len; i++) {
if (vec[i] == -1) {
continue;
}
if ((i * 2 < len) && (vec[i * 2] != -1 || vec[i * 2 + 1] != -1)) {
continue;
}
if (vec[i] < vec[minPos]) {
minPos = i;
}
}
while (minPos > 0) {
res.emplace_back(vec[minPos]);
minPos /= 2;
}
return res;
}
};
int main() {
vector<int> vec;
vec.emplace_back(0x3fffffff);
int v = 0;
while (cin >> v) {
vec.emplace_back(v);
}
vector<int> res = Main().getRes(vec);
for (int i = res.size() - 1; i >= 0; i--) {
cout << res[i] << " ";
}
}
查看23道真题和解析
腾讯音乐娱乐集团公司福利 283人发布