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

题目链接：?rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

我们可以通过画图发现规律，在后续遍历得到的结果中，，根节点肯定是在整个数组的最后面，而小于根结点的结点必然都是其左子树，这些结点都会位于数组的前半部分，而大于根结点的结点则都是根结点的右子树，这些结点都必然是其数组的后半部分，因此我们就可以通过递归来完成整个过程的判断

class Solution{public:bool VerifySquenceOfBST(vector<int> a){int len = a.size();if(len==0) return false;int root = a[len-1];vector<int> left;vector<int> right;int i = 0;for(; i<len-1; ++i){if(a[i]>root)break;left.push_back(a[i]);}int j = i;for(; j<len-1; ++j){if(a[j]<root)return false;right.push_back(a[j]);}bool flag1 = true;if(left.size())flag1 = VerifySquenceOfBST(left);bool flag2 = true;if(right.size())flag2 = VerifySquenceOfBST(right);return flag1&&flag2;}};

用爱生活，你会使自己幸福！用爱工作，你会使很多人幸福！

相关文章：

你感兴趣的文章：

标签云：