剑指Offer 二叉搜索树的后序遍历序列
2024-10-16 23:14:47
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路:
后续遍历数组的尾部为根节点,前面的部分,必然一部分为左子树,一部分为又子树,二叉搜索树,根节点左子树小于根节点的值,右子树大于。
所以我们只用遍历前面的部分,找到第一个大与根节点的,然后看后面是不是都是大于根节点的,如果是,size-1.
AC代码:
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
int sqsize=sequence.size();
int i=; if(sqsize==)
return false; while(i<sqsize)
{
while(sequence[i]<sequence[sqsize-])
i++;
while(sequence[i]>sequence[sqsize-])
i++; if(i!=sqsize-)
return false;
i=;
sqsize--;
}
return true;
}
};
最新文章
- PHP之call user func()函数
- 参数嗅探(Parameter Sniffing)(2/2)
- 【USACO】checker
- 面试感悟----一名3年工作经验的程序员应该具备的技能 JAVA 必读书
- Little shop of flowers - SGU 104 (DP)
- Windows应用程序要点
- Golang时间格式化
- Java并发编程之美之并发编程线程基础
- Hive与Hbase整合
- 【学习总结】GirlsInAI ML-diary day-7-数据类型转换
- python中的Matplot库和Gdal库绘制富士山三维地形图-参考了虾神的喜马拉雅山
- 详解margin: auto
- 关于vagrant一个虚拟机搭建多个项目配置(总结)
- 极路由hc5661安装tcpdump
- CF1129C Morse Code
- APP安全防护基本方法(混淆/签名验证/反调试)
- Android解析WindowManager(一)WindowManager体系
- UVA-1252 Twenty Questions (状压DP)
- ATOM &; Sublime Text 下MarkDown插件功能比较
- 如何更改tomcat7及以上版本内存设置