判断序列是否是二叉搜索树的后序遍历序列
题目要求：判断序列是否是二叉搜索树的后序遍历序列，给定一个序列，判断这个序列是否是二叉搜索树的一个正确的后序遍历序列。
算法思想：
我们知道，后续遍历根节点最后遍历，所以我们需要首先找到根节点。第二部就是根据二叉搜索树的性质了，二叉搜索树的左子树的值全都比根节点小，右子树的值全都比根节点的值大，所以我们需要运用递归，逐个去检查左子树和右子树是否符合这个规律即可。
算法实现：
1 #include<iostream>
2 using namespace std;
3
4 bool IsLRDofBST(int *data, int nLength){
5 if(data == NULL || nLength < 0){
6 return false;
7 }
8
9 int root = data[nLength - 1];
10
11 int i = 0;
12 for(; i < nLength - 1; ++i){ //找到左右子树分界点
13 if(data[i] > root){
14 break;
15 }
16 }
17
18 int j = i;
19 for(; j < nLength - 1; ++j){ //对右子树进行检查
20 if(data[j] < root)
21 return false;
22 }
23
24 bool left = true;
25 if(i > 0){
26 left = IsLRDofBST(data, i); //递归左子树
27 }
28
29 bool right = true;
30 if(i < nLength - 1){
31 right = IsLRDofBST(data + i, nLength - i - 1); //递归实现右子树
32 }
33
34 return (left && right);
35 }
36
37 int main(){
38 int tree[] = {
15, 6, 9, 11, 10, 8};
39 int len = sizeof(tree) / sizeof(int);
40 bool result = IsLRDofBST(tree, len);
41
42 if(result == true)
43 cout<<"The right answer"<<endl;
44 else
45 cout<<"The wrong answer"<<endl;
46
47 return 0;
48 } 1 #include
参考书籍：
《剑指offer》
题目要求：判断序列是否是二叉搜索树的后序遍历序列，给定一个序列，判断这个序列是否是二叉搜索树的一个正确的后序遍历序列。 算法思想： 我们知道，后续遍历根节点最后遍历，所以我们需要首先找到根节点。第二部就是根据二叉搜索树的性质了，二叉搜索树的左子树的值全都比根节点小，右子树的值全都比根节点的值大，所以我们需要运用递归，逐个去检查左子树和右子树是否符合这个规律即可。 算法实现： 1 #include