题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路：本题中的树为二叉搜索树，满足左<根<右
1）求出数组最后一个元素，为根节点
2）遍历，将所有连续小于sequence[n-1]的存入vector left中
3）将连续大于的存入vector right中 如果存在小于的，则直接返回false，无法构造二叉搜索树
4）然后对left进行递归处理，如果right为空则直接返回left_val
5）对right做递归处理，如果left为空，则直接返回right_val
6）否则返回(left_val && right_val)
注意点：本题中如果要遍历的数组的长度为1了，直接返回true，否则，递归永远返回false
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 class Solution { 5 public: 6 bool VerifySquenceOfBST(vector<int> sequence) { 7 8 //根节点为数组最后一个元素 9 int n = sequence.size(); 10 if(n == 0) 11 return false; 12 if(n == 1)//没有此种情况，不行 13 return true; 14 int root = sequence[n-1]; 15 vector<int> left;//存储左子树 16 vector<int> right;//存储右子树 17 //搜索二叉树，左子树均小于根，右子树均大于根 18 int i=0; 19 for(;i<n-1;i++) 20 { 21 if(sequence[i] > root) 22 { 23 break; 24 } 25 left.push_back(sequence[i]); 26 } 27 //搜索二叉树，右子树均大于根 28 for(int j = i;j<n-1;j++) 29 { 30 if(sequence[j] < root) 31 return false; 32 right.push_back(sequence[j]); 33 } 34 35 //遍历左子树 36 bool left_val = true; 37 left_val = VerifySquenceOfBST(left); 38 39 if(right.size()==0) //需要判断右子树是否为空，若只有左子树，返回 40 return left_val; 41 //遍历右子树 42 bool right_val = true; 43 right_val = VerifySquenceOfBST(right); 44 45 if(left.size()==0) 46 return right_val; 47 48 return (left_val && right_val); 49 } 50 }; 51 int main() 52 { 53 vector<int> a; 54 a.push_back(5); 55 a.push_back(4); 56 a.push_back(3); 57 a.push_back(2); 58 a.push_back(1); 59 60 Solution s; 61 bool r = s.VerifySquenceOfBST(a); 62 if(r) 63 { 64 cout<<"true"<<endl; 65 } 66 else 67 { 68 cout<<"false"<<endl; 69 } 70 return 0; 71 }
