题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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 - );
}
};

最新文章

  1. [BI项目记]-文档版本管理笔记
  2. 用Kibana和logstash快速搭建实时日志查询、收集与分析系统
  3. 基础学习day05---面向对象一类,对象、封装
  4. linux命令单次或组合样例
  5. zoj 3829 Known Notation
  6. Magento首页显示产品
  7. RMQ问题第一弹
  8. word,excel,ppt转Pdf,Pdf转Swf,通过flexpaper+swftools实现在线预览
  9. [array] leetcode - 48. Rotate Image - Medium
  10. 2019.03.29 bzoj5463: [APIO2018] 铁人两项(圆方树+树形dp)
  11. Confluence 6 重新获得附件指南
  12. django面试二
  13. 【原创】利用Office宏实现powershell payload远控
  14. Hibernate一对多单向关联和双向关联映射方法及其优缺点 (待续)
  15. andriod自定义视图
  16. Codeforces 441C Valera and Tubes
  17. [中英对照]The sysfs Filesystem | sysfs文件系统
  18. 20155307《Java程序设计》实验二实验报告
  19. Covariance 协方差分析
  20. jQuery中animate设置属性的一个问题

热门文章

  1. renren-fast-vue-动态路由
  2. python 模块-json
  3. [HNOI2011]卡农 题解
  4. [bzoj2287]消失之物 题解(背包dp)
  5. Echart使用js进行封装成函数
  6. 1、Monkey环境搭建
  7. 剑指offer第二版面试题1:数组中重复的数字(JAVA版)
  8. 力扣算法题—150. Evaluate Reverse Polish Notation
  9. WebStorage篇
  10. 使用Swagger2Markup归档swagger生成的API文档