ref:
1：根据先序遍历构造BST，构造过程中就判断是否构造成功。
第一个位置是root, 先序遍历结果是root，左子树，右子树；从左往右找第一个>root的位置，就是右子树开始的位置；接着往右遍历，如果发现<root的元素，则说明不可能构造。
2：打印结果时不能像Java那样string s, s+=int+"",真是fuck！！
#include#include #include using namespace std;int ele[1000+5];int n;struct node{ int val; node * left; node * right;};//别忘了fucking分号 node * tree;bool isValid = true;//判断能否构建BST,由于是在递归中，所以isValid应设成全局变量 int res[1000+5];//fucking string不能直接加一个两位int作为charint seq = 0;//变量取名叫index会编译错误，fuck!node * build(int l, int r){//根据ele[l]...ele[r]构建BST if(l > r) return NULL; node * root = new node(); root->val = ele[l]; root->left = NULL; root->right = NULL; if(l == r) return root; int rightStart = l+1; for(int i = l+1; i <=r; i++){ if(ele[i] > ele[l]){//先序遍历：（根，左子树，右子树），从第一个大于根节点的开始，之后的节点都是右子树 rightStart = i; break; }else{ rightStart++;//如果找不到，说明右子树为空，那么rightStart就被设为r+1，在求右子树的build()时就返回NULL } } //test //printf("rightStart = %d\n",ele[rightStart]); for(int i = rightStart; i <= r; i++){ if(ele[i] < ele[l]){//右子树中找到小于根的，说明不能构建成BST isValid = false; break; } } if(!isValid){ return NULL; } root->left = build(l+1,rightStart-1); root->right = build(rightStart, r); return root;}node * buildMirror(int l, int r){//构建BST的Mirror if(l > r){ return NULL; } node * root = new node(); root->val = ele[l]; root->left = NULL; root->right = NULL; if(l == r) return root; int rightStart = l+1;//右子树里都是小于根的节点 for(int i = l+1; i <= r; i++){ if(ele[i] < ele[l]){ rightStart = i; break; }else{ rightStart++; } } //test //printf("mirror rightStart = %d\n",ele[rightStart]); for(int i = rightStart; i <= r; i++){ if(ele[i] > ele[l]){ isValid = false; break; } } if(!isValid) { return NULL; } root->left = buildMirror(l+1,rightStart-1); root->right = buildMirror(rightStart,r); return root;}void printPost(node * p){ if(p == NULL){ return; } printPost(p->left); printPost(p->right); res[seq++] = p->val; }int main(){ freopen("in.txt","r",stdin); scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d",&ele[i]); } if(n == 1){//1个节点 printf("YES\n%d\n",ele[0]); return 0; } tree = build(0, n-1); if(isValid){ printf("YES\n"); printPost(tree); for(int i = 0; i