A1099 Build A Binary Search Tree

原题: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;

}
上一篇:学习代码


下一篇:JavaScript forEach() 方法