原题:https://pintia.cn/problem-sets/994805342720868352/problems/994805367987355648
一个给定的二叉搜索树,给定一个序列填入,然后求层序遍历。
难点主要是那个序列填入的方法,我是把序列首先排序,然后对BST进行中序遍历,得到由大到小的序列索引,这样直接输入就行了。
还有就是层序遍历使用队列。
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include<stack>
#include<queue>
using namespace std;
const int maxN = 101;
typedef int ElemT;
struct node {
ElemT data;
int lchild = -1;
int rchild = -1;
};
node T[maxN];
void inOrd(vector<int> &in,int index) {
if (index == -1)
return;
inOrd(in, T[index].lchild);
in.push_back(index);
inOrd(in, T[index].rchild);
}
//从index开始层序遍历
void LevelOrd(vector<int> &Le,int index) {
queue<int> q;
q.push(index);
while (!q.empty()) {
//访问
int temp = q.front();
Le.push_back(temp);
q.pop();
if (T[temp].lchild != -1)
q.push(T[temp].lchild);
if (T[temp].rchild != -1)
q.push(T[temp].rchild);
}
}
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> T[i].lchild >> T[i].rchild;
}
vector<ElemT> data(N);
for (int i = 0; i < N; i++) {
cin >> data[i];
}
sort(data.begin(), data.end());
//中序遍历
vector<int> in;
inOrd(in, 0);
//填入数据
for (int i = 0; i < N; i++) {
T[in[i]].data = data[i];
}
//LevelOrder
vector<int> Le;
LevelOrd(Le, 0);
for (int i = 0; i < N; i++) {
cout << T[Le[i]].data;
if (i < N - 1)
cout << " ";
else
cout << endl;
}
return 0;
}