BUPT OJ93 中序遍历序列

最新推荐文章于 2024-05-01 15:12:07 发布
最新推荐文章于 2024-05-01 15:12:07 发布
阅读量1.4k 收藏
点赞数
分类专栏： acm BUPT OJ
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/birdstorm_s/article/details/20306877
版权

题目描述

给出一个序列，判断该序列是不是某二叉搜索树的中序遍历序列，如果是输出"Yes"，否则输出"No"。
一颗带权二叉树是一颗二叉搜索树（二叉排序树），当且仅当对于任意一个节点，他的左子树中的所有权值小于当前节点的权值，且它的右子树中的所有权值均大于当前节点的权值。

输入格式

第一行 T (T≤10) 代表数据组数。
每组数据包括两行：
第一行为一个整数 N (1≤N ≤400) ,表示序列的长度。
第二行包含 N 个整数，表示这个这个序列，序列中的数的 x 范围为 (1≤x≤100000) 。

输出格式

每组数据，如果是二叉搜索树的中序遍历序列输出"Yes",否则输出"No"。

输入样例

2
4
1 2 3 4
4
1 3 2 4

输出样例

Yes
No

中心思路: 二叉排序树中序遍历必然为单调递增序列, 证明就不放了...超简单的一题


/*
USER_ID: test#birdstorm
PROBLEM: 93
SUBMISSION_TIME: 2014-03-01 18:15:10
*/
#include <stdio.h>
#define For(i,m,n) for(i=m;i<n;i++)
#define MAXN 405
 
main()
{
    int i, t, n, flag, a[MAXN];
    scanf("%d",&t);
    while(t--){
        flag=1;
        scanf("%d%d",&n,&a[0]);
        For(i,1,n){
            scanf("%d",&a[i]);
            if(a[i]<=a[i-1]) flag=0;
        }
        puts(flag?"Yes":"No");
    }
    return 0;
}


93. 中序遍历序列
恋&空的专栏
03-19 780
// 直接判断是不是从小到大的顺序，没有用二叉树。。。 #include int main() {     int n;     while(scanf("%d",&n)!=EOF){         while(n--){             int m;             scanf("%d",&m);             int buf[500];    
北邮oj93-中序遍历序列
qq_33782655的博客
03-28 216
注：所有的二叉排序树都有一个共同的特点：若对二叉排序树进行中序遍历，那么其遍历结果必然是一个递增序列 程序： #include<stdio.h> int main(){ int t; int n; int a[410]; int flag; scanf("%d",&t); for(int i=0;i<t...
中序遍历序列
Closure
03-09 1185
题目描述: 给出一个序列,判断该序列是不是某二叉搜索树的中序遍历序列，如果是输出"Yes",否则输出"No". 一颗带权二叉树是一 颗二叉搜索树(二叉排序树) ,当且仅当对于任意一个节点， 他的左子树中的所有权值小于当前节点的权值,且它的右子树中的所有权值均大于当前节点的权值。 输入格式: 第一行T(T≤10)代表数据组数。 每组数据包括两行: 第一行为一个整数N(1≤N≤400),表示序列...
二叉树的先序、中序、后序遍历序列
热门推荐
Bebr的博客
06-08 47万+
    二叉树的遍历主要有三种： （1）先(根)序遍历（根左右） （2）中(根)序遍历（左根右） （3）后(根)序遍历（左右根） 举个例子： 先(根)序遍历（根左右）：A B D H E I C F J K G 中(根)序遍历（左根右） : D H B E I A J F K C G 后(根)序遍历（左右根） : H D I E B J K F G C A     以后(根)序...
北邮OJ-93. 中序遍历序列-13计院上机C
听风就是雨
03-20 773
即判断此序列是否是一个非递减序列 题目描述 给出一个序列，判断该序列是不是某二叉搜索树的中序遍历序列，如果是输出”Yes”，否则输出”No”。 一颗带权二叉树是一颗二叉搜索树（二叉排序树），当且仅当对于任意一个节点，他的左子树中的所有权值小于当前节点的权值，且它的右子树中的所有权值均大于当前节点的权值。输入格式 第一行T(T≤10)代表数据组数。 每组数据包括两行： 第一行为一个整数N(1
126.中序遍历序列
略略略的博客
03-27 432
#include <bits/stdc++.h> using namespace std; const int maxn = 410; int a[maxn],c[maxn]; int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i = 0; i ...
【中序、后序遍历序列】【前序、中序遍历序列】构造二叉树
weixin_45799833的博客
09-29 565
java
二叉树的先序，中序，后序遍历序列
chengxuzx的博客
11-12 1万+
二叉树有三种遍历： 1.先序遍历： （根左右） 2.中序遍历 ： （左根右） 3.后序遍历： （左右根） 举个例子：（以下动画图转载自https://blog.csdn.net/chinesekobe/article/details/110874773）： 先(根)序遍历（根左右）：A B D H I E J C F K G 中(根)序遍历（左根右） : H D I B E J A F K C G 后(根)序遍历（左右根） : H I D J E ...
由中序遍历序列和后序遍历序列构造二叉树（递归实现）
DUAN的专栏
08-07 1207
#include #include typedef struct bitree_node { char data; struct bitree_node * lchild, * rchild; }bitree_node, *binary_tree; int locate_data( char arr[], int left, int right, char key ) {
【数据结构】---树：中序遍历
qq_54185425的博客
01-13 1万+
中序遍历，是数据结构中树的遍历方式之一。特点：左、根、右。每次遍历时，先遍历左节点的数据，之后遍历本节点，最后遍历右节点，循环往复，直至树中数据遍历完成。二叉查找树进行中序遍历后，返回的序列是排好序的。数据结构方面的内容刚刚接触，讲解不够深刻，还望谅解。
BUPT OJ 中序遍历树
wcnmcsdn的博客
01-24 909
水题。 开始看错，当成按照每个节点代表的字符顺序访问了，后来改完就可以了。 #include #include #include using namespace std; char func[101]; bool relation[100][100]={false}; bool visited[100]={false}; string result; string temp; void dfs
(二叉树）从中序与后序遍历序列构造二叉树
zhou_pp的博客
07-24 522
后序遍历的最后一个值是树的根节点，在中序遍历中找到该节点，根据中序遍历的特点（左子树-根-右子树)，所以在中序遍历中，把根节点左边的值都放进左子树递归，把根节点右边的值都放进右子树递归。 class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { int len1=inord...
二叉树的前序遍历，中序遍历，后序遍历-详解-配套例题
爱吃橘子的小翟
04-03 1万+
二叉树作为数据结构中一种简单而且重要的数据结构，他的存储结构和算法都相对比较简单，因此他也显得特别重要，因为很多问题都可以抽象为二叉树的问题。 在这里我们对于二叉树的基本概念不做详细介绍，我们这里主要介绍二叉树的前序遍历，中序遍历，和后序遍历三种问题和如何通过他的前序遍历，中序遍历，后序遍历构造相应的二叉搜索树的问题。 在这之前，我们先简单了解一下二叉树的三种遍历到底是什么样子的。 我的记忆方式为： 前序遍历-DLR（根...
二叉树的先序、中序、后序遍历超详解
代码是程序员的语言，博客是思想的桥梁，连接你我，共享智慧之光。
05-31 10万+
以上图为基础 ①前序遍历的方式是：首先访问根节点，然后访问左子树，最后访问右子树。 前序遍历序列：F C A D B E H G M ②中序遍历的方式是：首先访问左子树，接着访问根结点，最后访问右子树。 中序遍历序列：A C B D F H E M G ③后序遍历的方式是：首先访问左子树，接着访问右子树，最后访问根结点。 后序遍历序列：A B D C H M G E F ④相同的特点： 左子树总是在右子树的之前遍历。 遍历都可以用递归的方式来描述。 中序遍历的序列中任取一个结点，该结点的左子树右子树一定分.
【算法】从前序与中序遍历序列构建二叉树
最新发布
Conner7的博客
05-01 1471
与二叉树的遍历相反，能不能通过二叉树的遍历结果确定一棵二叉树，怎样确定？今年做到过的一道笔试题便是以此题为基础，故记录分享于此。
BUPT OJ 中序遍历序列
wcnmcsdn的博客
01-14 366
水 #include #include #include using namespace std; int main() { int t,n,x; cin>>t; while(t--) { vectorBeforeSort; vectorAfterSort; cin>>n; while(n--) { cin>>x; BeforeSor
北邮机试 | bupt oj | 93. 中序遍历序列
我是一块小石头
03-12 344
中序遍历序列 时间限制 1000 ms 内存限制 65536 KB 题目描述 给出一个序列，判断该序列是不是某二叉搜索树的中序遍历序列，如果是输出"Yes"，否则输出"No"。 一颗带权二叉树是一颗二叉搜索树（二叉排序树），当且仅当对于任意一个节点，他的左子树中的所有权值小于当前节点的权值，且它的右子树中的所有权值均大于当前节点的权值。 输入格式 第一行T(T≤10)代表数据组数。 每组...
画出用非递归方式对二叉树进行先序、中序、后序遍历的算法流程图
06-01
[中序遍历非递归算法流程图](https://cdn.jsdelivr.net/gh/linyimin-bupt/pictures-for-picbed/img/20211105173826.png) 3. 后序遍历 ![后序遍历非递归算法流程图]...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值