PAT Build A Binary Search Tree

题目大意：对于一个给定的二叉树，给一个序列，把这个序列中的数字填入此二叉树，使此二叉树为二叉排序树。

思路：

1)保证此二叉树为BST->二叉树中序遍历序列有序则为BST->把有序序列按中序遍历插入树中2)output层次遍历序列

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cstdlib>#include<algorithm>#include<queue>#include<set>#include<map>#include<vector>#include<cmath>#define ll __int64using namespace std;const int INF=0x3fffffff;struct Node{    int data;    int l,r;}tree[205];int n;int a[205];int k;void InorderInsert(int root){    if(root!=-1){        InorderInsert(tree[root].l);        tree[root].data=a[k++];        InorderInsert(tree[root].r);    }}void TraversalOutput(int root){    k=0;    queue<int>q;    q.push(0);    while(!q.empty()){        int i=q.front();        q.pop();        if(i!=-1){            cout<<tree[i].data;            k++;            if(k!=n){                cout<<" ";            }            q.push(tree[i].l);            q.push(tree[i].r);        }    }}int main(){    //freopen("d://Test.txt","r",stdin);    cin>>n;    for(int i=0;i<n;i++){        int l,r;        cin>>l>>r;        tree[i].l=l;        tree[i].r=r;    }    for(int i=0;i<n;i++){        cin>>a[i];    }    sort(a,a+n);    k=0;    InorderInsert(0);    TraversalOutput(0);    return 0;}