本文共 1249 字，大约阅读时间需要 4 分钟。

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数N（<=1000）。随后一行给出N个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出“YES”，然后在下一行输出该树后序遍历的结果。数字间有1个空格，一行的首尾不得有多余空格。若答案是否，则输出“NO”。

78 6 5 7 10 8 11

YES5 7 6 8 11 10 8

78 10 11 8 6 7 5

YES11 8 10 7 5 6 8

78 6 8 5 10 9 11

NO

思路：由二叉树的性质，左子树的值都小于根节点的值，右子树的值度大于等于根节点的值，所以我们可以递归遍历这棵树进行判断，题目中说给的序列可能是原树前序遍历的结果，也有可能是镜像以后树的前序遍历序列，我们可以先判断是不是原树的前序遍历结果，如果不是在进行镜像树的判断。

在判断时候我们可以通过查找当前这棵树的左右子树，由于是前序遍历的结果，所以左子树结束的位置就是右子树开始的位置，所以这时候我们判断一下左子树结束位置和右子树开始位置之差是不是1，然后在递归进行判断。

#include 
   
    using namespace  std;const int maxn=1050;int a[maxn];bool isMarr;vector
    
      v;int n;void gettree(int root,int tail){    if(root>tail) return;    int i=root+1;    int j=tail;    if(!isMarr)    {        while(i<=tail&&a[root]>a[i]) i++;        while(j>root&&a[root]<=a[j]) j--;    }    else    {        while(i<=tail&&a[root]<=a[i]) i++;        while(j>root&&a[root]>a[j]) j--;    }//    cout<
     <<" "<
      
       <
       
        >n;    for(int i=0; i
        
         >a[i]; isMarr=false; gettree(0,n-1);// cout<
         
          <
         
        
       
      
    
   

转载地址：http://wbgsi.baihongyu.com/