时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路：
注：二叉搜索树的特点是根节点大于左孩子，小于右孩子。后序遍历的最后一个节点是根节点，因此小于根节点的为左子树，大于根节点发构成右子树。
BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。采用递归的方法。
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.empty()) return false; return Judge(sequence,0,sequence.size()-1); } bool Judge(vector<int> &s,int l,int r) { //只存在左子树或右子树的情况 if(l >= r) return true; //确定以根节点数据将原序列分成两份，左边都小于根节点，右边都大于根节点 int i = r; while(i > l && s[i-1] > s[r]) i--; for(int j = i-1 ; j >= l; --j) if(s[j] > s[r]) return false; return Judge(s,l,i-1)&&Judge(s,i,r-1); } };
同理，对于二叉搜索树的前序遍历序列也可以使用相类似的方法来做。
原文链接: https://www.cnblogs.com/whiteBear/p/12547817.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/336958
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
