当前位置:网站首页>Whether the same binary search tree (25 points)
Whether the same binary search tree (25 points)
2022-04-23 08:41:00 【Huaihua second affectionate】
Given an insertion sequence, a binary search tree can be uniquely determined . However , A given binary search tree can be obtained from a variety of different insertion sequences . For example, in sequence {2, 1, 3} and {2, 3, 1} Insert a binary search tree that is initially empty , All get the same result . So for the input of various insertion sequences , You need to determine if they can generate the same binary search tree .
Input format :
The input contains several sets of test data . The... Of each group of data 1 Line gives two positive integers N (≤10) and L, They are the number of inserted elements in each sequence and the number of sequences to be checked . The first 2 Line is given N Positive integers separated by spaces , As the initial insertion sequence . And then L That's ok , Each line gives N An inserted element , Belong to L A sequence to check .
Simplicity , We guarantee that every insertion sequence is 1 To N An arrangement of . When read N by 0 when , Mark end of input , Don't process this data .
Output format :
For each set of sequences that need to be checked , If the binary search tree generated by it is the same as that generated by the corresponding initial sequence , Output “Yes”, Otherwise output “No”.
sample input :
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
sample output :
Yes
No
No
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
typedef Node* Tree;
Tree insert(Tree BT, int x) {
if (!BT) {
BT = new (Node);
BT->data = x;
BT->left = BT->right = NULL;
} else if (x < BT->data)
BT->left = insert(BT->left, x);
else if (x > BT->data)
BT->right = insert(BT->right, x);
return BT;
}
bool judge(Tree a, Tree b) {
if (a == NULL && b == NULL)
return true;
else if ((a != NULL && b == NULL) || (a == NULL && b != NULL))
return false;
else if (a->data == b->data)
return judge(a->left,b->left)&&judge(a->right,b->right);
return false;
}
int main(){
int n,l,k;
while(cin>>n&&n){
cin>>l;
Tree BT=NULL;
int x;
for(int i=0;i<n;i++){
cin>>x;
BT=insert(BT,x);
}
for(int i=0;i<l;i++){
Tree Temp=NULL;
for(int j=0;j<n;j++){
cin>>x;
Temp=insert(Temp,x);
}
if(judge(Temp,BT))cout<<"Yes\n";
else cout<<"No\n";
}
}
}
版权声明
本文为[Huaihua second affectionate]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204230835222766.html
边栏推荐
猜你喜欢
LLVM之父Chris Lattner:编译器的黄金时代
ESP32程序下载失败,提示超时
idea底栏打开services
IDEA导入commons-logging-1.2.jar包
RCC introduction of Hal Library
php基于哈希算法出现的强弱比较漏洞
Notes on 30 steps of introduction to Internet of things of yangtao electronics STM32 III. Explanation of new cubeide project and setting
MySQL查询两张表属性值非重复的数据
2022-04-22 OpenEBS云原生存储
测试你的机器学习流水线
随机推荐
计算神经网络推理时间的正确方法
Go语言自学系列 | golang嵌套结构体
Yangtao electronic STM32 Internet of things introduction 30 steps notes 1. The difference between Hal library and standard library
DOM learning notes - traverse all element nodes of the page
Consensus Token:web3.0生态流量的超级入口
'恶霸' Oracle 又放大招,各大企业连夜删除 JDK。。。
RPC procedure
虚拟线上展会-线上vr展馆实现24h沉浸式看展
After a circle, I sorted out this set of interview questions..
Stm32f103zet6 [development of standard library functions] - Introduction to library functions
Navicat remote connection MySQL
LeetCode396.旋转数组
php基于哈希算法出现的强弱比较漏洞
LaTeX数学公式
求简单类型的矩阵和
请提前布局 Star Trek突破链游全新玩法,市场热度持续高涨
K210学习笔记(二) K210与STM32进行串口通信
uni-app和微信小程序中的getCurrentPages()
根据字节码获取类的绝对路径
【58】最后一个单词的长度【LeetCode】