二叉搜索树的后序遍历序列

【题目描述】

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

【解题思路】

在后序遍历得到的序列中，最后一个数字是树的根节点的数值。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。第一部分和第二部分可以使用递归的方式进行判断。

【代码实现】

 1 class Solution {
 2 public:
 3     bool VerifySquenceOfBST(vector<int> sequence) {
 4         if(sequence.empty())
 5             return false;
 6            int root=sequence.back();//后序遍历的最后一个节点为根节点
 7         //在二叉搜索树中左子节点小于根节点，其中i为左右子树的分支点，根据i的值判断左右子树的存在性及其位置
 8         vector<int> leftSeq;
 9         int i;
10         for(i=0;i<sequence.size()-1;++i)
11         {       
12             if(sequence[i]>root)
13                 break;
14             else
15                 leftSeq.push_back(sequence[i]);
16         }
17         //在二叉搜索树种右子节点大于根节点，如果存在小于根节点的数值直接退出
18         vector<int> rightSeq;
19         int j;
20         for(j=i;j<sequence.size()-1;++j)
21         {
22             if(sequence[j]<root)
23                 return false;
24             else
25                 rightSeq.push_back(sequence[j]);
26         }
27 
28         //判断左子树是否是二叉搜索树
29         bool left=true;
30         if(i>0)
31             left=VerifySquenceOfBST(leftSeq);
32 
33         //判断右子树是否是二叉搜索树
34         bool right=true;
35         if(i<sequence.size()-1)
36             right=VerifySquenceOfBST(rightSeq);
37 
38         return (left&&right);
39     }
40 };