当前位置:编程学习 > C/C++ >>

二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
输入:
每个测试案例包括2行:
第一行为1个整数n(1<=n<=10000),表示数组的长度。
第二行包含n个整数,表示这个数组,数组中的数的范围是[0,100000000]。
输出:
对应每个测试案例,如果输入数组是某二叉搜索树的后序遍历的结果输出Yes,否则输出No。
样例输入:
7
5 7 6 9 11 10 8
4
7 4 6 5
样例输出:
Yes
No
代码AC:
思想:需要遍历树,二叉排序树的特点是 lchild.key < root.key < rchild.key
那么我们使用分治思想,先利用上面特点将左右子树分开,遇到第一个大于root.key的之后(右边)就是又子树,那么当我们在遍历又子树的时候如果遇到小于root.key的情况,那么就是错误的序列。。。。
 
[cpp] 
// 使用分治!   
  
#include <stdio.h>  
#include <stdlib.h>  
  
long int *num;  
  
int fun( long int low, long int high )  
{  
    long int i, l, tmp_idx, flag = 1;  
      
    if( low >= high )  
    {  
        return 1;  
    }  
      
    for( i = low; i < high , num[i] < num[high]; i++ );  
      
    tmp_idx = i;  
      
    for( i; i < high; i++ )  
    {  
         if( num[i] < num[high] )  
         {  
             return 0;  
         }  
    }  
      
    if( fun( low, tmp_idx - 1 ) == 0 )  
    {  
        return 0;  
    }  
      
    if( fun( tmp_idx + 1, high ) == 0 )  
    {  
        return 0;     
    }      
      
    return 1;  
}  
  
int main()  
{  
    long int n, i, low, high;  
      
    while( scanf("%ld", &n) != EOF )  
    {  
           num = ( long int* )malloc( sizeof( long int ) * n );  
             
           for( i = 0; i < n; i++ )  
           {  
                scanf("%ld", &num[i]);  
           }  www.zzzyk.com
             
           if( fun( 0, n - 1 ) )  
           {  
               printf("Yes\n");  
           }  
           else  
           {  
               printf("No\n");  
           }  
             
           free( num );  
    }  
      
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,