剑指offer-二叉搜索树的后序遍历序列

题目描述

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

解题思路

由于二叉搜索树具有以下性质：根节点大于左子树中所有结点，同时小于右子树中所有结点。所以可以先找到根结点然后划分左右子树判断是否符合。题中给了二叉搜索树的后序遍历序列，所以根结点即为序列最后一个数字，从第一个结点开始依次与根结点比较，直到找到第一个大于根结点的数字，这样此结点左边便为左子树，此结点与根节点之间的数字为右子树。然后遍历右子树中的结点，如果发现小于根结点的数字即不符合性质返回false；如果均小于根结点，接着递归遍历左右子树，划分子树并判断是否符合性质。

代码

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> v) {
 4         if(v.size())
 5             return Verify(v,0,v.size()-1);
 6         return false;
 7     }
 8     bool Verify(vector<int> v,int f,int l){
 9         if(f<l){
10             int m=f;
11             while(v[m]<v[l])
12                 m++;
13             int i=m;
14             while(i<l)
15                 if(v[i++]<v[l])
16                     return false;
17             return Verify(v,f,m-1)&&Verify(v,m,l-1);
18         }
19         return true;
20     }
21 };