剑指offer——35二叉树的后序遍历
2024-10-07 19:48:18
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
题解:
这道题,一开始以为将后序遍历排序后的得到中序遍历,然后利用后序遍历和中序遍历进行二叉树的重组,但是由于后序遍历未必是BST树的,故得到的中序遍历未必是正确的;
所以,根据后序遍历,直接对树的左右子树进行判断。
class Solution {
public:
bool VerifySquenceOfBST(vector<int> sequence) {
if (sequence.size() == )return false;
return isBST(sequence, , sequence.size() - );
}
bool isBST(vector<int>v, int L, int R)
{
if (L >= R)return true;
int root = v[R];
int i = L;
while (v[i] < root)++i;//找到左子树
int j = i;
while (j < R)if (v[j++] < root)return false;//判断右子树
return isBST(v, L, i - ) && isBST(v, i, R - );
}
};
最新文章
- [BI项目记]-文档版本管理笔记
- 用Kibana和logstash快速搭建实时日志查询、收集与分析系统
- 基础学习day05---面向对象一类,对象、封装
- linux命令单次或组合样例
- zoj 3829 Known Notation
- Magento首页显示产品
- RMQ问题第一弹
- word,excel,ppt转Pdf,Pdf转Swf,通过flexpaper+swftools实现在线预览
- [array] leetcode - 48. Rotate Image - Medium
- 2019.03.29 bzoj5463: [APIO2018] 铁人两项(圆方树+树形dp)
- Confluence 6 重新获得附件指南
- django面试二
- 【原创】利用Office宏实现powershell payload远控
- Hibernate一对多单向关联和双向关联映射方法及其优缺点 (待续)
- andriod自定义视图
- Codeforces 441C Valera and Tubes
- [中英对照]The sysfs Filesystem | sysfs文件系统
- 20155307《Java程序设计》实验二实验报告
- Covariance 协方差分析
- jQuery中animate设置属性的一个问题