剑指offer---2、二叉搜索树的后序遍历序列
2024-09-06 15:46:10
剑指offer---2、二叉搜索树的后序遍历序列
一、总结
一句话总结：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
认真看题：注意题目中是二叉搜索树，二叉搜索树就有二叉搜索树的那些规律
1、二叉搜索树的后序遍历序列 的解题思路是什么？
BST的后序序列的合法序列是，对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 : ) 。
2、二叉树的问题的注意事项是什么？
递归：一般是 递归 来做
增一个函数：一般要重新写一个函数来做递归
二、内容在总结中
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
参考代码：java
class Solution {
bool judge(vector<int>& a, int l, int r){
//只有一个元素的时候
if(l >= r) return true;
//找右子树
int i = r;
while(i > l && a[i - 1] > a[r]) --i;
//判断左子树
for(int j = i - 1; j >= l; --j) if(a[j] > a[r]) return false;
//分别判断左右子树
return judge(a, l, i - 1) && (judge(a, i, r - 1));
}
public:
bool VerifySquenceOfBST(vector<int> a) {
if(!a.size()) return false;
return judge(a, 0, a.size() - 1);
}
};
最新文章
- DB String Split sample
- Backpack | & ||
- hdf第一周完了,突然时间静止.,醒了就早点去公司上班,再努力一点
- 指针属性直接赋值 最好先retain 否则内存释放导致crash
- GPRS Sniffing Tutorial
- CentOS7 备忘录
- android 带边框的圆角按钮
- KMP学习笔记
- [LeetCode] 347. Top K Frequent Elements 解题思路 - Java
- getpwent()
- apache的配置参数
- Docker Hub工作流程-Docker for Web Developers(6)
- odoo 权限问题
- 22 python 初学（类，面向对象）
- [04-05]box框模型(Box Model)定义了元素框处理元素内容、内边距、边框和外边距的方式
- AI大道理头尾标识
- 自定义控件（视图）2期笔记12：View的滑动冲突之 外部拦截法
- ubuntu 卸载 google-chrome
- BZOJ1096 ZJOI2007 仓库建设 【斜率优化DP】
- IDEA下载与安装