[PAT解题报告] Is It a Binary Search Tree
给定二叉搜索树或者其镜像的前序遍历序列，先判断是否可能，如果可能，求它的后序遍历序列。
简单题，就是个二叉树还原问题。我们从前序遍历开始还原出整个树，还原方法是递归的——
就是对当前节点，根据左右子树信息，可以确定它的值应该在一个范围内。我写的函数make1,
make2就是从二叉搜索树，或者其镜像还原出它本身,参数p1,p2的值决定了当前这个节点应该在它父亲的左边还是右边，递归下去就好了。
我们可以用数组代替指针，尽管节点left
right仍然是指针（地址），但它指向的是一个真正存在的位置，而不是我们new出来的空间，这样就不用
delete了。make1和make2都是尽可能多地还原树，如果最后用不了那么多节点——说明有矛盾。否则我们正好还原了这个树，再做一次后序遍历即可。
代码：
#include <cstdio>
#include <cstring>
using namespace std;
struct node {
int val;
node *left,*right;
};
node a[1024];
bool first;
int n;
node *make1(node *a,int &now,node *p1, node *p2) {
// val < p1->val, val >= p2->val
if (now >= n) {
return 0;
}
node *root = 0;
if (((p1 == 0) || (a[now].val < p1->val)) && ((p2 == 0) || (a[now].val >= p2->val))) {
root = a + (now++);
root->left = make1(a, now, root, p2);
root->right = make1(a, now, p1, root);
}
return root;
}
node *make2(node *a,int &now,node *p1, node *p2) {
// val >= p1->val, val < p2->val
if (now >= n) {
return 0;
}
node *root = 0;
if (((p1 == 0) || (a[now].val >= p1->val)) && ((p2 == 0) || (a[now].val < p2->val))) {
root = a + (now++);
root->left = make2(a, now, root, p2);
root->right = make2(a, now, p1, root);
}
return root;
}
void dfs(node *root) {
if (root) {
dfs(root->left);
dfs(root->right);
if (first) {
first = false;
}
else {
putchar(' ');
}
printf("%d",root->val);
}
}
int main() {
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%d",&a[i].val);
a[i].left = a[i].right = 0;
}
int now;
node *root = make1(a, now = 0, 0, 0);
if (now < n) {
root = make2(a, now = 0, 0, 0);
}
if (now >= n) {
puts("YES");
first = true;
dfs(root);
puts("");
}
else {
puts("NO");
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1043
投递科大讯飞等公司10个岗位 >
