(熟练！重要！)二叉搜索树 BST
题目大意
判断给定序列是否是一个BST或镜像BST树的先序遍历序列，如果是则输出该树的后序遍历序列。
思路
根据给定序列创建BST树，求出它的先序遍历和镜像树的先序遍历（即原树遍历时按照根->右->左），与原序列比较。
AC代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <cstdio>
#include <vector>
#include <map>
#include<algorithm>
using namespace std;
struct node {
int key;
node* lchild;
node* rchild;
};
vector<int> input, pre1, pre2;
void create(node* &root, int v) {
if (root == NULL) {
root = new node;
root->key = input[v];
root->lchild = root->rchild = NULL;
return;
}
if (input[v] < root->key)
create(root->lchild, v);
else create(root->rchild, v);
}
void preorder(node* p) {
if (p == NULL)return;
pre1.push_back(p->key);
preorder(p->lchild);
preorder(p->rchild);
}
void mirrorpreorder(node* p) {
if (p == NULL)return;
pre2.push_back(p->key);
mirrorpreorder(p->rchild);
mirrorpreorder(p->lchild);
}
bool space = false;
void postorder(node* p) {
if (p == NULL)return;
postorder(p->lchild);
postorder(p->rchild);
if (space == false) {
printf("%d", p->key);
space = true;
}
else printf(" %d", p->key);
}
void mirrorpostorder(node* p) {
if (p == NULL)return;
mirrorpostorder(p->rchild);
mirrorpostorder(p->lchild);
if (space == false) {
printf("%d", p->key);
space = true;
}
else printf(" %d", p->key);
}
int main() {
int i, n;
scanf("%d", &n);
input.resize(n);
node* root = NULL; //不要漏掉将NULL赋值给root!!!
for (i = 0;i < n;i++) {
scanf("%d", &input[i]);
create(root, i);
}
preorder(root);
mirrorpreorder(root);
if (pre1 == input) {
printf("YES\n");
postorder(root);
}
else if (pre2 == input) {
printf("YES\n");
mirrorpostorder(root);
}
else printf("NO");
return 0;
}
另
可以根据BST的特性，不用建立树直接求。但我没看懂QAQ... https://blog.csdn.net/liuchuo/article/details/52160455
