题目1367：二叉搜索树的后序遍历序列-CSDN博客

题目描述：

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

输入：

每个测试案例包括2行：

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

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

输出：

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

样例输入：

75 7 6 9 11 10 847 4 6 5

样例输出：

YesNo

答疑：

解题遇到问题?分享解题心得?讨论本题请访问： http://t.jobdu.com/thread-8090-1-1.html

#include <stdio.h>
#include <stdlib.h>
 
#define false 0
#define true 1
 
int judge_bst(int *arr, int len);
 
int main()
{
    int i, n, flag, arr[100001];
 
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i ++)
            scanf("%d", &arr[i]);
        
        flag = judge_bst(arr, n);
        (flag == 1) ? printf("Yes\n") : printf("No\n");
    }
 
    return 0;
}
 
int judge_bst(int *arr, int len)
{
    int i, j, root;
    
    // 递归终止条件
    if (len <= 0)
        return true;
 
    root = *(arr + len - 1);
 
    // 区分左子树
    for (i = 0; i < len - 1; i ++) {
        if (*(arr + i) > root)
            break;
    }
 
    // 查找右子树是否符合要求
    for (j = i; j < len - 1; j ++) {
        if (*(arr + j) < root) 
            return false;
    }
 
    // 递归的判断左右子树是否符合要求
    int left, right;
    left = true;
    left = judge_bst(arr, i);
 
    right = true;
    right = judge_bst(arr + i, len - 1 - i);
 
    return (right && left);
}