数据结构与算法-7-28 搜索树判断

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数N（$\le$1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

7
8 6 5 7 10 8 11

输出样例1:

YES
5 7 6 8 11 10 8

输入样例2:

7
8 6 8 5 10 9 11

输出样例2:

NO

这道题生成两棵树：镜像和非镜像，然后先序遍历即可

或者只生成一棵树，遍历的时候正着遍历一遍，再反着遍历亦可。

代码：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct node{
  int data;
  node *lchild, *rchild;
};
node *T = NULL, *_T = NULL;
vector<int> pre, _pre, post, input;

void insert(node* &root, int n){
  if(root == NULL){
    root = new node;
    root->data = n;
    root->lchild = root->rchild = NULL;
    return; 
  }
  if(n >= root->data)
    insert(root->rchild, n);
  else
    insert(root->lchild, n);
  return;
}

void _insert(node* &root, int n){
  if(root == NULL){
    root = new node;
    root->data = n;
    root->lchild = root->rchild = NULL;
    return; 
  }
  if(n >= root->data)
    _insert(root->lchild, n);
  else
    _insert(root->rchild, n);
  return;
}

void preOrder(node* root, bool _){
  if(root == NULL) return;
  if(!_) pre.push_back(root->data);
  else _pre.push_back(root->data);
  preOrder(root->lchild, _);
  preOrder(root->rchild, _);
}

void postOrder(node* root){
  if(root == NULL) return;
  postOrder(root->lchild);
  postOrder(root->rchild);
  post.push_back(root->data);
}

int main(){
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    int num;
    cin >> num;
    insert(T, num);
    _insert(_T, num);
    input.push_back(num);
  }
  preOrder(T, false);
  preOrder(_T, true);
  if(input == pre){
    cout << "YES" << endl;
    postOrder(T);
  }else if(input == _pre){
    cout << "YES" << endl;
    postOrder(_T);
  }else{
    cout << "NO" << endl;
    return 0;
  }
  for(int i = 0; i < post.size(); i++){
    cout << post[i];
    if(i != post.size() - 1) cout << ' ';
  }
  return 0;
}