剑指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 递归求解

 class Solution {

 public:

     bool VerifySquenceOfBST(vector<int> sequence) {}    //判断某数组是不是二叉搜索树的后序遍历序列

         if(sequence.empty())

             return false;

         int index;

         int begin = ;

         int end = sequence.size()-;

         int root = sequence[end];

         for(index = begin;index<end;index++)    //左子结点小于根节点

             if(sequence[index]>root)

                 break;

         for(int j = index;index<end;index++)    //右子结点大于根结点

             if(sequence[index]<root)

                 return false;

         bool left = true;

         vector<int> left_sq(sequence.begin(),sequence.begin()+index);

         if(index>begin)

             left = VerifySquenceOfBST(left_sq);    //判断左子树是不是二叉搜索树

         bool right = true;

         vector<int> right_sq(sequence.begin()+index+,sequence.end());

         if(index<end-)

             right = VerifySquenceOfBST(right_sq);    //判断右子树是不是二叉搜索树

         return left&&right;

     }

 };

3.2 非递归求解

 class Solution {

 public:

     bool VerifySquenceOfBST(vector<int> sequence) {    //判断某数组是不是二叉搜索树的后序遍历序列

         int backIdx = sequence.size();

         if(backIdx==) return false;

         int forIdx = ;

         while(--backIdx)  // backIdx=1时退出循环

         {

             while(sequence[forIdx]<sequence[backIdx])  forIdx++;     // forIdx从前往后扫描left部分

             while(sequence[forIdx]>sequence[backIdx])  forIdx++;     // forIdx从前往后继续扫描，主要扫right部分

             if(forIdx<backIdx) return false;    // 如果原序列是二叉搜索树BST的后序遍历序列，则终止时forIdx=backIdx

             forIdx=;                           // 将forIdx拉回序列起点继续扫

         }

         return true;

     }

 };

4 C++完整代码

 #include<cstdio>

 #include<vector>

 using namespace std;

 class Solution{

 public:

     bool VerifySquenceOfBST(vector<int> sequence)

     {

         int len = sequence.size();

         if (len <= )

             return false;

         vector<int> left, right;

         int root = sequence[len - ];

         int i = ;

         while (i<len - )  // 处理left部分

         {

             if (sequence[i]>root)

                 break;

             left.push_back(sequence[i]);

             i++;

         }

         int j = i; // 处理right部分，此时i为left部分最后一个结点的下标

         while (j<len - )

         {

             if (sequence[j]<root)

                 return false;

             right.push_back(sequence[j]);

             j++;

         }

         bool bleft = true; // 应初始化为true，left部分是BST序列，才能调用VerifySquenceOfBST()

         if (i != )

             bleft = VerifySquenceOfBST(left); // i为left部分最后一个结点的下标 ，i!=0表示有左子树

         bool bright = true;

         if (i != len - )

             bright = VerifySquenceOfBST(right);  // i!= len-1表示有右子树

         return (bleft && bright);

     }

 };

 // 以下为测试部分

 int main()

 {

     Solution sol;

     vector<int> vec1 = { , , , , , ,  };

     vector<int> vec2 = { , , , , , ,  };

     vector<int> vec3 = { , , ,  };

     bool res1 = sol.VerifySquenceOfBST(vec1);

     bool res2 = sol.VerifySquenceOfBST(vec2);

     bool res3 = sol.VerifySquenceOfBST(vec3);

     printf("%d\n", res1);

     printf("%d\n", res2);

     printf("%d\n", res3);

     system("pause");

     return ;

 }

参考资料

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

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

巴特西