首页 > 代码库 > 牛客 看看数组是不是二叉搜索树的后序遍历序列
牛客 看看数组是不是二叉搜索树的后序遍历序列
class Solution { bool judge(vector<int>& a, int left, int right) { if(left>=right) return true; int i=right; //此时数组的right就是根 while(i>left&&a[i-1]>a[right]) --i; //找到左子树,i-1就是左子树根 for(int j=i-1;j>=left;--j) if(a[j]>a[right]) //如果左子树中的数存在大于根的数,则不是二叉搜索 return false; for(int j=i;j<right;j++) if(a[j]<a[right])//找到右子数树,右边的数必须都大于根才行 return false; return judge(a, left, i - 1) && (judge(a, i, right- 1)); //如果左子树都小于根,开始判断左子树和右子树是否符合二叉搜索树,从i到right-1就是右子树,right-1就是右子树根 }public: bool VerifySquenceOfBST(vector<int> a) { if(!a.size()) return false; return judge(a, 0, a.size() - 1); } };
牛客 看看数组是不是二叉搜索树的后序遍历序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。