PAT 1099 Build A Binary Search Tree

题意：

依次给出各点的左右孩子结点号， 接着再往其中存入一组数字。要求构成二叉搜索树。

注意点：

1. 理解题目含义。 构建树时，给的输入是0~n各点各自的左右孩子，而非我之前理解的用先序遍历存入的孩子信息。

2. 注意加上-1的判断。

//628K	94MS
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<stack>
#include<vector>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define M 2500

int lchild[M],rchild[M];
int n;
void BuildTree()
{
	int l,r;
	for(int i = 0 ;i < n; i++)
	{
		scanf("%d%d",&l,&r);
		lchild[i] = l;
		rchild[i] = r;
	}
}

int k;
int num[M],ans[M];
void InsertTree(int node)
{
	if(node == -1 || k >= n)
		return ;
	InsertTree(lchild[node]);
	ans[node] = num[k++];
	InsertTree(rchild[node]);
}
void printTree(int node)
{
	queue<int> q;
	q.push(node);
	printf("%d",ans[node]);
	while(!q.empty())
	{
		node = q.front();
		q.pop();
		if(node != 0)
			printf(" %d", ans[node]);
		if(lchild[node] != -1)
			q.push(lchild[node]);
		if(rchild[node] != -1)
			q.push(rchild[node]);
	}
	cout<<endl;
}


int main(){
	
	scanf("%d",&n);
	if(n == 0)
		return 0;
	BuildTree();
	for(int i = 0;i < n; i++)
	{
		scanf("%d",&num[i]);
	}
	sort(num,num+n);
	k = 0;
	InsertTree(0);
	printTree(0);
	return 0;
}