数据结构不难11
2019/3/22更新
后序遍历
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
在参与过了美食节之后，小Hi和小Ho在别的地方又玩耍了一阵子，在这个过程中，小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树！
小Ho对这棵二叉树爱不释手，于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母，并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会，重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样，日子安稳的过了两天。
这天，小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果，但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上，小球和木棍等零件散落了一地！
小Ho损失了心爱的玩具，正要嚎啕大哭起来，所幸被小Hi发现了，劝说道：“别着急，这不是零件都还在么？拼起来不就是了？”
“可是我忘记了二叉树长什么样子了！”小Ho沮丧道。
“这个简单，你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么，利用这两个信息就可以还原出整棵二叉树来哦！”
“这样么？！！”小Ho止住了泪水，问道：“那要怎么做呢？”
没错！小Ho在这一周遇到的问题便是：给出一棵二叉树的前序和中序遍历的结果，还原这棵二叉树并输出其后序遍历的结果。
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为一个由大写英文字母组成的字符串，表示该二叉树的前序遍历的结果。
每组测试数据的第二行为一个由大写英文字母组成的字符串，表示该二叉树的中序遍历的结果。
对于100%的数据，满足二叉树的节点数小于等于26。
输出
对于每组测试数据，输出一个由大写英文字母组成的字符串，表示还原出的二叉树的后序遍历的结果。
样例输入
AB
BA
样例输出
BA
AC代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<memory>
#include<cstring>
using namespace std;
char p[30],m[30];
int vis[30],Len;
void _find(int L,int R)
{
int i,j,pos=0;
for(i=1;i<=Len&&!pos;i++)
for(j=L;j<=R&&!pos;j++)
if(p[i]==m[j]) {
pos=j;
break;
}
if(L<pos) _find(L,pos-1);
if(R>pos) _find(pos+1,R);
cout<<m[pos];
}
int main()
{
int i,j;
scanf("%s",p+1);
scanf("%s",m+1);
Len=strlen(p+1);
_find(1,Len);
return 0;
}
第二题 最近公共祖先
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
小Ho最近发现了一个神奇的网站！虽然还不够像58同城那样神奇，但这个网站仍然让小Ho乐在其中，但这是为什么呢？
“为什么呢？”小Hi如是问道，在他的观察中小Ho已经沉迷这个网站一周之久了，甚至连他心爱的树玩具都弃置一边。
“嘿嘿，小Hi，你快过来看！”小Ho招呼道。
“你看，在这个对话框里输入我的名字，在另一个对话框里，输入你的名字，再点这个查询按钮，就可以查出来……什么！我们居然有同一个祖祖祖祖祖爷爷？”
“诶，真是诶……这个网站有点厉害啊。”小Hi不由感叹道。
“是啊，这是什么算法啊，这么厉害！”小Ho也附和道。
“别2，我说的是他能弄到这些数据很厉害，而人类的繁殖树这种层数比较浅的树对这类算法的要求可是简单的不得了，你都能写出来呢！”小Hi道。
“啊？我也能写出来？可是……该从哪开始呢？”小Ho困惑了。
小Ho要面临的问题是这样的，假设现在他知道了N个人的信息——他们的父亲是谁，他需要对于小Hi的每一次提问——两个人的名字，告诉小Hi这两个人的是否存在同一个祖先，如果存在，那么他们的所有共同祖先中辈分最低的一个是谁？
提示：不着急，慢慢来，另外我有一个问题：挖掘机技术哪家强？！
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2~N+1行，每行分别描述一对父子关系，其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i，分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M，表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行，每行分别描述一个询问，其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i，分别表示小Hi询问中的两个名字。
对于100%的数据，满足N<=102，M<=102, 且数据中所有涉及的人物中不存在两个名字相同的人（即姓名唯一的确定了一个人）。
输出
对于每组测试数据，对于每个小Hi的询问，输出一行，表示查询的结果：如果根据已知信息，可以判定询问中的两个人存在共同的祖先，则输出他们的所有共同祖先中辈分最低的一个人的名字，否则输出-1。
样例输入
11
JiaYan JiaDaihua
JiaDaihua JiaFu
JiaDaihua JiaJing
JiaJing JiaZhen
JiaZhen JiaRong
JiaYuan JiaDaishan
JiaDaishan JiaShe
JiaDaishan JiaZheng
JiaShe JiaLian
JiaZheng JiaZhu
JiaZheng JiaBaoyu
3
JiaBaoyu JiaLian
JiaBaoyu JiaZheng
JiaBaoyu LinDaiyu
样例输出
JiaDaishan
JiaZheng
-1
AC代码 ---java实现
import java.util.HashMap;
import java.util.Scanner;
public class Main {
private HashMap<String,Integer>nodeMap;
private Node[]nodes;
private int index;
private int ancestorIndex;
public Main(){
this.nodeMap=new HashMap<String,Integer>();
this.nodes=new Node[1001];
this.index=0;
this.ancestorIndex=-1;
}
private void reset(){
for(int i=0;i<this.index;i++){
this.nodes[i].isVisited=false;
}
this.ancestorIndex=-1;
}
private int getNode(String nodeName){
if(!this.nodeMap.containsKey(nodeName)){
this.nodes[this.index]=new Node(nodeName);
this.nodeMap.put(nodeName, this.index);
this.index++;
}
return this.nodeMap.get(nodeName);
}
private void visit(int nodeIndex){
if(nodeIndex>=0&&nodeIndex<this.index){
if(this.nodes[nodeIndex].isVisited){
this.ancestorIndex= nodeIndex;
return;
}else{
this.nodes[nodeIndex].isVisited=true;
int parentIndex=this.nodes[nodeIndex].parentIndex;
this.visit(parentIndex);
}
}
}
public void addNode(String parent,String child){
int parentIndex=this.getNode(parent);
int childIndex=this.getNode(child);
if(parentIndex>=0&&parentIndex<this.index
&&childIndex>=0&&childIndex<this.index){
this.nodes[childIndex].parentIndex=parentIndex;
}
}
public void getAncestor(String first,String second){
int firstIndex=this.getNode(first);
int secondIndex=this.getNode(second);
this.visit(firstIndex);
this.visit(secondIndex);
if(this.ancestorIndex>=0&&this.ancestorIndex<this.index){
this.nodes[this.ancestorIndex].print();
}else{
System.out.println("-1");
}
this.reset();
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
Main ancestor=new Main();
int n=scanner.nextInt();
for(int i=0;i<n;i++){
String first=scanner.next();
String second=scanner.next();
ancestor.addNode(first, second);
}
int m=scanner.nextInt();
for(int i=0;i<m;i++){
String first=scanner.next();
String second=scanner.next();
ancestor.getAncestor(first, second);
}
}
}
class Node{
public String name;
public int parentIndex;
public boolean isVisited;
public Node(String name){
this.name=name;
this.parentIndex=-1;
this.isVisited=false;
}
public void print(){
System.out.println(this.name);
}
}
无根树变有根树
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
<dl class="des">
描述
给定一棵包含 <var>N</var> 个节点的无根树，小Hi想知道如果指定其中某个节点 <var>K</var> 为根，那么每个节点的父节点是谁？
15013494395080.png
输入
第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N。
以下N-1行每行包含两个整数 a 和 b，代表ab之间存在一条边。 1 ≤ a, b ≤ N。
输入保证是一棵树。
输出
输出一行包含 N 个整数，分别代表1~N的父节点的编号。对于 K 的父节点输出0。
样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1
AC代码
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
int n, p[MAXN];
vector<int> G[MAXN];
void dfs(int u, int fa) { //递归转化为以u为根的子树，u的父亲为fa
int d = G[u].size(); //节点u的相邻点的个数
for(int i = 0; i < d; ++i) { //循环遍历跟这个节点相连接的d个节点。
int v = G[u][i]; //节点u的第i个相邻点v
if(fa != v) dfs(v, p[v] = u); //把v的父亲节点设为u，然后递归转化为以v为根的子树
//一定要判断v是否和其父亲节点相等！
}
}
int main() {
int root;
//cin >> root;
cin >> n>>root;
for(int i = 1; i <= n-1; i++) { //输入n-1条边
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
//指定根节点。
p[root] = 0; //设定根节点的父亲节点为-1，代表根节点没有父亲节点。
dfs(root, 0);
for(int i = 1; i <= n; ++i) {
cout << p[i] <<" ";
}
return 0;
}
是二叉搜索树吗
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
二叉搜索树指一棵空树或者具有下列性质的二叉树：
-
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
-
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
-
任意节点的左、右子树也分别为二叉查找树；
-
没有键值相等的节点。
已知现在有N个节点，键值恰好为1~N；同时给定N-1对节点的父子关系，请你判断这些节点是否构成一棵二叉搜索树。
如果不构成二叉搜索树，请输出错误代码：
错误代码1: N个节点不构成树；
错误代码2: N个节点不构成二叉树；
错误代码3: N个节点不构成二叉搜索树。
由于以上错误具有包含关系，所以你只需输出最小的错误代码。
如果构成二叉搜索树，请将这棵二叉搜索树依照一下格式序列化输出：
二叉搜索树T的序列化表示S(T)：
-
T是空树，S(T) = ()
-
否则设R是T的根， S(T) = (RS(T的左子树)S(T的右子树))
例如：
2
/
1 3
(2(1()())(3()()))
1
2
(1()(2()()))
输入
输入包含多组数据。
第一行包含一个整数T，代表数据组数。(1 ≤ T ≤ 10)
对于每组数据，第一行包含一个整数N，表示节点个数。 (1 ≤ N ≤ 10000)
以下N-1行，每行包含两个整数a和b，代表键值a的节点是键值b的节点的父亲。 (1 ≤ a, b ≤ N)
输出
对于每组数据，如果不构成二叉搜索树，输出ERRORX，其中X是错误代码。否则输出序列化表示。
样例输入
4
3
1 2
3 2
4
1 2
1 3
1 4
3
1 2
1 3
3
2 1
2 3
样例输出
ERROR1
ERROR2
ERROR3
(2(1()())(3()()))
AC代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 1e4 + 10;
vector<int> vc[M];
int fa[M] , ch[M][2] , f[M] , n , emmm , num[M];
void init() {
for(int i = 1 ; i <= n ; i++) {
f[i] = i;
vc[i].clear();
}
}
int find(int x) {
if(x == f[x]) return f[x];
return f[x] = find(f[x]);
}
int cnt;
void cau(int u) {
int len = vc[u].size();
if(len == 2) {
if(vc[u][0] == vc[u][1] || vc[u][0] == u || vc[u][1] == u) emmm = 1;
cau(vc[u][0]);
num[cnt++] = u;
cau(vc[u][1]);
}
if(len == 1) {
if(vc[u][0] == u) emmm = 1;
if(vc[u][0] > u) {
num[cnt++] = u;
cau(vc[u][0]);
}
else {
cau(vc[u][0]);
num[cnt++] = u;
}
}
if(len == 0) {
num[cnt++] = u;
}
}
void dfs(int u) {
int len = vc[u].size();
if(len == 1) {
if(u > vc[u][0]) {
putchar('(');
printf("%d" , vc[u][0]);
dfs(vc[u][0]);
putchar(')');
putchar('(');
putchar(')');
}
else {
putchar('(');
putchar(')');
putchar('(');
printf("%d" , vc[u][0]);
dfs(vc[u][0]);
putchar(')');
}
}
if(len == 2) {
putchar('(');
printf("%d" , vc[u][0]);
dfs(vc[u][0]);
putchar(')');
putchar('(');
printf("%d" , vc[u][1]);
dfs(vc[u][1]);
putchar(')');
}
if(len == 0) {
putchar('(');
putchar(')');
putchar('(');
putchar(')');
}
}
int main() {
int t;
scanf("%d" , &t);
while(t--) {
cnt = 0;
scanf("%d" , &n);
memset(fa , -1 , sizeof(fa));
int flag = 0;
init();
for(int i = 1 ; i <= n - 1 ; i++) {
int u , v;
scanf("%d%d" , &u , &v);
vc[u].push_back(v);
int a = find(u) , b = find(v);
if(a == b) {
flag = 1;
}
else {
f[b] = a;
}
if(fa[v] == -1) {
fa[v] = u;
continue;
}
else {
flag = 1;
}
}
if(flag) {
printf("ERROR1\n");
}
else {
int tmp = 0;
for(int i = 1 ; i <= n ; i++) {
if(vc[i].size() == 0) continue;
sort(vc[i].begin() , vc[i].end());
if(vc[i].size() > 2) {
tmp = 1;
break;
}
}
if(tmp) {
printf("ERROR2\n");
}
else {
emmm = 0;
int root = 1;
for(int i = 1 ; i <= n ; i++) {
if(fa[i] == -1) {
root = i;
break;
}
}
cau(root);
for(int i = 1 ; i < cnt ; i++) {
if(num[i] <= num[i - 1]) {
emmm = 1;
break;
}
}
if(emmm) {
printf("ERROR3\n");
}
else {
putchar('(');
printf("%d" , root);
dfs(root);
putchar(')');
puts("");
}
}
}
}
return 0;
}
