P9 中序遍历树并判断是否为二叉搜索树 (15 分)

2024-03-04 15:32

本文主要是介绍P9 中序遍历树并判断是否为二叉搜索树 (15 分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对给定的有N个节点(N>=0)的二叉树,给出中序遍历序列,并判断是否为二叉搜索树。

题目保证二叉树不超过200个节点,节点数值在整型int范围内且各不相同。

输入格式:
第一行是一个非负整数N,表示有N个节点

第二行是一个整数k,是树根的元素值

接下来有N-1行,每行是一个新节点,格式为r d e 三个整数,

r表示该节点的父节点元素值(保证父节点存在);d是方向,0表示该节点为父节点的左儿子,1表示右儿子;e是该节点的元素值

输出格式:
首先输出二叉树的中序遍历序列,每个元素占一行。对于空树,不输出任何内容。

然后如果给定的树是二叉搜索树,输出Yes 否则输出No

输入样例:
在这里插入图片描述

对于图片中的二叉树:

3
20
20 0 10
20 1 25
输出样例:
10
20
25
Yes

题解

最开始我试图用数组的方式来存二叉树,但是中序遍历的时候出现了问题。
后来还是改成了指针的形式

#include <iostream>
#include <cstdio> 
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> res, tmp;
int n;
const int N = 5000;
int arr[N];
struct tree{int val;tree* left;tree* right;tree(int x){val = x;left = right = nullptr;}
};
void inorder(tree* root){if(!root) return;inorder(root->left);cout<<root->val<<endl;res.push_back(root->val);inorder(root->right);
}
int main(){unordered_map<int, tree*> mp;cin>>n;int x, d, e;tree* root = nullptr;for(int i = 1; i <= n; i ++){cin>>x;if(i != 1){cin>>d>>e;auto r = mp[x];tmp.push_back(e);if(d == 0) { //左儿子 r->left = new tree(e);mp[e] = r->left;}else{ //右儿子 r->right = new tree(e);mp[e] = r->right;}}else{root = new tree(x);mp[x] = root;tmp.push_back(x);}}inorder(root); sort(tmp.begin(), tmp.end());if(res == tmp) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

这篇关于P9 中序遍历树并判断是否为二叉搜索树 (15 分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/773627

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

这15个Vue指令,让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件,按住 Control 和回车键再显示它吗?小菜一碟: <template

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

POJ1269 判断2条直线的位置关系

题目大意:给两个点能够确定一条直线,题目给出两条直线(由4个点确定),要求判断出这两条直线的关系:平行,同线,相交。如果相交还要求出交点坐标。 解题思路: 先判断两条直线p1p2, q1q2是否共线, 如果不是,再判断 直线 是否平行, 如果还不是, 则两直线相交。  判断共线:  p1p2q1 共线 且 p1p2q2 共线 ,共线用叉乘为 0  来判断,  判断 平行:  p1p

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close