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

缺乏、安全感 2022-03-20 02:48 174阅读 0赞

**何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ**

**题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=9][http_ac.jobdu.com_problem.php_cid_1039_pid_9]**

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

**输入：**

每个测试案例包括2行：

第一行为1个整数n(1<=n<=10000)，表示数组的长度。

第二行包含n个整数，表示这个数组，数组中的数的范围是\[0,100000000\]。

**输出：**

对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No。

**样例输入：**

5 7 6 9 11 10 8

7 4 6 5

**样例输出：**

Yes

代码AC：

思想：需要遍历树，二叉排序树的特点是 lchild.key < root.key < rchild.key

那么我们使用分治思想，先利用上面特点将左右子树分开，遇到第一个大于root.key的之后(右边)就是又子树，那么当我们在遍历又子树的时候如果遇到小于root.key的情况，那么就是错误的序列。。。。

// 使用分治！ 
    
    #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]);
               }
               
               if( fun( 0, n - 1 ) )
               {
                   printf("Yes\n");
               }
               else
               {
                   printf("No\n");
               }
               
               free( num );
        }
        
        return 0;
    }

[http_ac.jobdu.com_problem.php_cid_1039_pid_9]: http://ac.jobdu.com/problem.php?cid=1039&pid=9