题目描述
链接
给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果
分析
- 注意每个地方二叉查找树的定义不同，看清题目
- 写insert函数的时候，不要忘记左右子树为NULL
- 镜像二叉查找树实际就是遍历的时候，把左右次序更换下就好了！
#include<bits/stdc++.h>
using namespace std;const int maxn = 1005;
struct node{int data;node *lchild;node *rchild;
}nodes[maxn];int a[maxn], n;void insert(node *&root, int x){if(root == NULL){root = new node;root->data = x;root->lchild = NULL; //不要忘记!root->rchild = NULL; //不要忘记!return;}if(x < root->data) insert(root->lchild, x); //题目定义不同else insert(root->rchild, x);
}node *create(){node *root = NULL;for(int i=0;i<n;i++){insert(root, a[i]);}return root;
}vector<int> b,c,d;
void preorder(node *root){if(root==NULL) return;b.push_back(root->data);preorder(root->lchild);preorder(root->rchild);
}void preorder2(node *root){if(root==NULL) return;c.push_back(root->data);preorder2(root->rchild);preorder2(root->lchild);
}void postorder(node *root){if(root==NULL) return;postorder(root->lchild);postorder(root->rchild);d.push_back(root->data);
}void postorder2(node *root){if(root==NULL) return;postorder2(root->rchild);postorder2(root->lchild);d.push_back(root->data);
}int main(){cin>>n;for(int i=0;i<n;i++){cin>>a[i];}node *root = create();preorder(root);preorder2(root);bool flag1 = true, flag2 = true;for(int i=0;i<n;i++){if(a[i] != b[i]) {flag1 = false; break;}}for(int i=0;i<n;i++){if(a[i] != c[i]) {flag2 = false; break;}}if(flag1){postorder(root);cout<<"YES"<<endl;for(int i=0;i<n;i++){if(i==0) cout<<d[i];else cout<<" "<<d[i];}cout<<endl;}else if(flag2){postorder2(root);cout<<"YES"<<endl;for(int i=0;i<n;i++){if(i==0) cout<<d[i];else cout<<" "<<d[i];}cout<<endl;}else{cout<<"NO"<<endl;}}
