剑指offer23：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。输出Yes OR No。

1 题目描述

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

2 思路和方法

　　二叉搜索树：二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

　　递归求解：

（1）从第0位开始，找到第一位比根节点大的元素，记录此位置i。在此位置之前都属于左子树（此时已经断定左子树都小于根节点）

（2）检查右子树是否都大于跟节点（从第i位开始，到根节点前）

（3）判断左右子树是否都属于二叉搜索树。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

非递归求解：

　6
/
3 8
/ /
2 5 7 9

2 5 3 7 9 8 6

　　左子树一定比右子树小，因此去掉根结点后，数字分为left，right两部分，right部分的最后一个数字是右子树的根，且它比左子树所有结点的值大，因此我们可以每次只看有子树是否符合条件即可，即使到达了左子树，左子树也可以看出由左右子树组成的树还像右子树那样处理.

3 C++核心代码

3.1 递归求解

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {}    //判断某数组是不是二叉搜索树的后序遍历序列
 4         if(sequence.empty())
 5             return false;
 6         int index;
 7         int begin = 0;
 8         int end = sequence.size()-1;
 9         int root = sequence[end];    
10         for(index = begin;index<end;index++)    //左子结点小于根节点
11             if(sequence[index]>root)
12                 break;
13         for(int j = index;index<end;index++)    //右子结点大于根结点
14             if(sequence[index]<root)
15                 return false;
16         bool left = true;
17         vector<int> left_sq(sequence.begin(),sequence.begin()+index);
18         if(index>begin)
19             left = VerifySquenceOfBST(left_sq);    //判断左子树是不是二叉搜索树
20         bool right = true;
21         vector<int> right_sq(sequence.begin()+index+1,sequence.end());
22         if(index<end-1)
23             right = VerifySquenceOfBST(right_sq);    //判断右子树是不是二叉搜索树
24         return left&&right;
25     }
26 };

View Code

3.2 非递归求解

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {    //判断某数组是不是二叉搜索树的后序遍历序列
 4         int backIdx = sequence.size();
 5         if(backIdx==0) return false;
 6 
 7         int forIdx = 0;
 8         while(--backIdx)  // backIdx=1时退出循环
 9         {
10             while(sequence[forIdx]<sequence[backIdx])  forIdx++;     // forIdx从前往后扫描left部分
11             while(sequence[forIdx]>sequence[backIdx])  forIdx++;     // forIdx从前往后继续扫描，主要扫right部分
12 
13             if(forIdx<backIdx) return false;    // 如果原序列是二叉搜索树BST的后序遍历序列，则终止时forIdx=backIdx
14             forIdx=0;                           // 将forIdx拉回序列起点继续扫
15         }
16         return true;
17     }
18 };

View Code

4 C++完整代码

 1 #include<cstdio>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 class Solution{
 7 public:
 8     bool VerifySquenceOfBST(vector<int> sequence)
 9     {
10         int len = sequence.size();
11         if (len <= 0) 
12             return false;
13         vector<int> left, right;
14         int root = sequence[len - 1];
15         int i = 0;
16         while (i<len - 1)  // 处理left部分 
17         {
18             if (sequence[i]>root) 
19                 break;
20             left.push_back(sequence[i]);
21             i++;
22         }
23         int j = i; // 处理right部分，此时i为left部分最后一个结点的下标 
24         while (j<len - 1)
25         {
26             if (sequence[j]<root) 
27                 return false;
28             right.push_back(sequence[j]);
29             j++;
30         }
31         bool bleft = true; // 应初始化为true，left部分是BST序列，才能调用VerifySquenceOfBST()    
32         if (i != 0) 
33             bleft = VerifySquenceOfBST(left); // i为left部分最后一个结点的下标 ，i!=0表示有左子树 
34         bool bright = true;
35         if (i != len - 1) 
36             bright = VerifySquenceOfBST(right);  // i!= len-1表示有右子树
37         return (bleft && bright);
38     }
39 };
40 // 以下为测试部分 
41 int main()
42 {
43     Solution sol;
44     vector<int> vec1 = { 2, 5, 3, 7, 9, 8, 6 };
45     vector<int> vec2 = { 5, 7, 6, 9, 11, 10, 8 };
46     vector<int> vec3 = { 7, 4, 6, 5 };
47     bool res1 = sol.VerifySquenceOfBST(vec1);
48     bool res2 = sol.VerifySquenceOfBST(vec2);
49     bool res3 = sol.VerifySquenceOfBST(vec3);
50 
51     printf("%d
", res1);
52     printf("%d
", res2);
53     printf("%d
", res3);
54 
55     system("pause");
56     return 0;
57 }

View Code

参考资料

https://blog.csdn.net/cdatreides/article/details/81701523

https://blog.csdn.net/lzuacm/article/details/51317617