1099 Build A Binary Search Tree

题目大意

给出一棵树的结构，再给出一串数字序列，让你数字填空，使得这棵树为二叉搜索树。

---

思路解析

见到BST就要想到中序遍历，已经形成PAT套路了。 本题也不例外，先将所给数字升序排列，然后在中序遍历的过程中填空就可以。

---

示例代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
public:
	int val;
	int left = -1, right = -1;
};
vector<node> vec;
vector<int> v2;//v2是元素库
int index = 0;
int maxdeep = 0;
void inorder(int v) {
	if (v == -1) return;
	if (vec[v].left != -1) 
		inorder(vec[v].left);
	vec[v].val = v2[index];
	index++;
	if (vec[v].right != -1) 
		inorder(vec[v].right);
}
vector<vector<int>> res(110);
void level(int v,int deep) {
	if (v == -1)return;
	if (deep > maxdeep) maxdeep = deep;
	res[deep].push_back(vec[v].val);
	level(vec[v].left, deep + 1);
	level(vec[v].right, deep + 1);
}
int main() {
	int n;
	scanf("%d", &n);
	vec.resize(n);
	v2.resize(n);
	for (int i = 0; i < n; i++) {
		int left, right;
		scanf("%d %d", &left, &right);
		if (left != -1) vec[i].left = left;
		if (right != -1) vec[i].right = right;
	}
	for (int i = 0; i < n; i++)
		scanf("%d", &v2[i]);
	sort(v2.begin(), v2.end());
	inorder(0);
	level(0, 0);
	for (int i = 0; i <= maxdeep; i++) {
		for (int j = 0; j < res[i].size(); j++) {
			if (i == maxdeep  && j == res[j].size() - 1) //最后一个元素
				printf("%d", res[i][j]);
			else 
				printf("%d ", res[i][j]);			
		}
	}
	return 0;
}