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

地址：http://ac.jobdu.com/problem.php?pid=1367

题目1367：二叉搜索树的后序遍历序列

题目描述：

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

输入：

每个测试案例包括2行：

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

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

输出：

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

样例输入：

75 7 6 9 11 10 847 4 6 5

样例输出：

YesNo

答疑：

解题遇到问题?分享解题心得?讨论本题请访问：

解题思路：

1、从后向前扫描数组，建立一个二叉搜索树（原理：在数组中，根节点都在其叶子节点的后方）

2、后序遍历该二叉树

3、比较后序遍历结果与原数组是否相同。相同，Yes；不相同，No。

#include 
    
     #include 
     
      int a[10000];int p;struct treeNode {    int data;    treeNode *left;    treeNode *right;}; void createNode(treeNode *root, int k) {    if(root->left == NULL && k < root->data) {        treeNode *tmp = (treeNode *)malloc(sizeof(treeNode));        tmp->left = tmp->right = NULL;        tmp->data = k;        root->left = tmp;    }    else if(root->left != NULL && k < root->data) {        createNode(root->left, k);    }    else if(root->right == NULL && k > root->data) {        treeNode *tmp = (treeNode *)malloc(sizeof(treeNode));        tmp->left = tmp->right = NULL;        tmp->data = k;        root->right = tmp;    }    else if(root->right != NULL && k > root->data) {        createNode(root->right, k);    }} treeNode *createTree(int n){    treeNode *root = (treeNode *)malloc(sizeof(treeNode));    root->left = root->right = NULL;    root->data = a[n - 1];    for(int i = n - 2; i >= 0; i --) {        createNode(root, a[i]);    }    return root;} bool posterTraverse(treeNode *root) {    bool flag = true;    if(root->left != NULL)        flag = posterTraverse(root->left);    if(root->right != NULL && flag)        flag = posterTraverse(root->right);    if(!flag)        return false;    if(a[p ++] != root->data)        return false;    return true;} int main(){    int n;    while(scanf("%d", &n) != EOF) {        p = 0;        for(int i = 0; i < n; i ++) {            scanf("%d", &a[i]);        }        treeNode *root = createTree(n);        bool flag = posterTraverse(root);        if(flag)            printf("Yes\n");        else            printf("No\n");    }    return 0;}/**************************************************************    Problem: 1367    Language: C++    Result: Accepted    Time:20 ms    Memory:1324 kb****************************************************************/
     
    

1、把数组最后一个元素（根节点）与数组中从左至右每一个元素i进行比较

2、当元素i大于最后一个元素时，停止循环。至此，将数组划分为左子树（0 ~ i-1）和右子树（i ~ n-2）

3、使右子树中的每一个元素j与最后一个元素比较，只要有一个元素j大于最后一个元素，则No

代码作者：sunpicker

#include 
    
     int a[10001];int buildtree(int left,int right){    if(left>=right)        return 1;    else    {        int i,j;        for(i=left;i
     
      =a[right])                break;        for(j=i;j
      
     
    

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