本文主要是介绍题目1367：二叉搜索树的后序遍历序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- 输入：
-
每个测试案例包括2行：
第一行为1个整数n(1<=n<=10000)，表示数组的长度。
第二行包含n个整数，表示这个数组，数组中的数的范围是[0,100000000]。
- 输出：
-
对应每个测试案例，如果输入数组是某二叉搜索树的后序遍历的结果输出Yes，否则输出No。
解题思路：
首先我们观察题目：二叉搜索树，后序遍历两个知识点。
二叉搜索树，用于搜索，因此内部节点没有重复的元素。另外，满足二叉树的性质，左子树都比自己小，右子树都比自己大。那么可想而知，如果按照后序遍历，先左后右最后自己的顺序来遍历树，数组的最后一个元素肯定是自己（父节点），然后剩余的部分分成两个部分，第一部分都比自己小（左子树部分），第二部分都比自己大（右子树部分），因此套用这个关系就可以循环检验出是否是二叉搜索树的后序遍历了。
代码：
#include<stdio.h>
#include<stdlib.h>
#define Max 10001typedef struct tree
{int data;struct tree *left;struct tree *right;
}SearchTree;int a[Max];int judge(int i , int j)
{if(i == j)return 1;else{int k = j - 1;while(k >= i){if(a[k] > a[j])k--;elsebreak;}int flag = k;while(k >= i){if(a[k] < a[j])k--;elsebreak;}if(k == i - 1){if(a[i] > a[j] ||a[j - 1] < a[j])//判断是否是单孩子树return judge(i,j - 1);elsereturn judge(i,flag) && judge(flag + 1, j - 1);}elsereturn 0;}
}int main()
{int n;while(scanf("%d",&n) != EOF){SearchTree *search = new SearchTree;for(int i = 0; i < n; i++)scanf("%d",&a[i]);if(judge(0,n - 1) == 1)printf("Yes\n");elseprintf("No\n");}
}
这篇关于题目1367：二叉搜索树的后序遍历序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
