【剑指Offer面试编程题】题目1367:二叉搜索树的后序遍历序列--九度OJ
2024-10-08 13:28:49
- 题目描述:
-
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
- 输入:
-
每个测试案例包括2行:
第一行为1个整数n(1<=n<=10000),表示数组的长度。
第二行包含n个整数,表示这个数组,数组中的数的范围是[0,100000000]。
- 输出:
-
对应每个测试案例,如果输入数组是某二叉搜索树的后序遍历的结果输出Yes,否则输出No。
样例输入:
7
5 7 6 9 11 10 8
4
7 4 6 5
样例输出:
Yes
No
【解题思路】对于二叉搜索树我们首先要明确一点:给出二叉搜索树也就意味着给出了的树的中序遍历序列,因为将节点排序后就是中序遍历序列,所以本题目中给出树的后序遍历序列,那么我们就可以唯一的确定一棵树。根据二叉搜索树的特点:树的根节点大于左子树任意元素,小于右节点任意元素,我们可以知道,后序遍历的最后一个节点8即根节点,可以将树分为5 7 6左子树,9 11 10右子树。然后分别对左右子树应用后序遍历的特点继续往下分。
在我们递归分左右子树的过程中需要我们判断序列是否满足二叉树的情况,也即:给定的序列是否满足前面数字比序列的最后数小,其余数比序列最后数大的规律。不满足就判断这是非法的二叉树后序序列。
AC code:
#include <cstdio>
#include <vector>
using namespace std; bool flg; void check(vector<int> &vec,const int&a,const int&b)
{
int idx=a;
if(a==b)
return;
while(vec[idx]<vec[b])++idx;
if(idx!=a)
check(vec,a,idx-1);
if(idx==b)
return;
int tag=idx;
while(vec[idx]>vec[b])++idx;
if(idx!=b)
{
flg=false;
return ;
}else
check(vec,tag,b-1);
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
vector<int> vec;
flg=true;
for(int i=0;i<n;++i)
{
int tt;
scanf("%d",&tt);
vec.push_back(tt);
}
check(vec,0,n-1);
if(flg)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
/**************************************************************
Problem: 1367
User: huo_yao
Language: C++
Result: Accepted
Time:10 ms
Memory:1024 kb
****************************************************************/题目链接:http://ac.jobdu.com/problem.php?pid=1367
九度-剑指Offer习题全套答案下载:http://download.csdn.net/detail/huoyaotl123/8276299
最新文章
- centos6.5 nginx-1.8.0和ftp搭建图片服务器
- 关于在程序中 文件新生成 在用os.system()程序对新生成的文件处理 举个栗子 如下:
- Thinkphp 中 distinct 的用法
- iOS - CoreLocation 定位
- Android开发遇到的坑(1):Java中List的安全删除问题
- GitHub 操作流程示例
- 更简单地进行Auto Layout--SnapKit 支持swift
- python 虎扑注册检查脚本
- Windows下管理Python安装包
- jQuery autoResize
- KEILC51可重入函数及模拟栈浅析
- C#核编之一个简单的C#程序
- win7(32 bit) + IE8 环境,IE8无法弹窗(错误提示:“此网页上的错误可能会使它无法正确运行”),有关的系统注册信息损坏——解决方法
- 同步 VS 异步
- [搬运] DotNetAnywhere:可供选择的 .NET 运行时
- HDU 1584(蜘蛛牌 DFS)
- The world is in my hands
- markdown基础入门
- POJ 1659
- [dpdk] dpdk多线程任务调度