洛谷——【数据结构1-2】二叉树

题目

【深基16.例1】淘汰赛

题目描述

有 $2^n$（$n\le 7$）个国家参加世界杯决赛圈且进入淘汰赛环节。已经知道各个国家的能力值，且都不相等。能力值高的国家和能力值低的国家踢比赛时高者获胜。1 号国家和 2 号国家踢一场比赛，胜者晋级。3 号国家和 4 号国家也踢一场，胜者晋级……晋级后的国家用相同的方法继续完成赛程，直到决出冠军。给出各个国家的能力值，请问亚军是哪个国家？

输入格式

第一行一个整数 $n$，表示一共 $2^n$ 个国家参赛。

第二行 $2^n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的国家的能力值（$1\le i\le 2^n$）。

数据保证不存在平局。

输出格式

仅一个整数，表示亚军国家的编号。

样例 #1

样例输入 #1

3
4 2 3 1 10 5 9 7

样例输出 #1

1

基本思路：

• 这道题数据量比较小(n>=7)，我是暴力模拟过的，从第n层开始选拔，每次选拔人数会减少一半，到第一层即v[0]，只剩下1人，这个人就是冠军，第二层较小的即为亚军。

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
int n;
vector<pair<int,int>> v[10];//分别保存能力值和编号void solve(){cin>>n;int len=pow(2,n);for(int i=1;i<=len;i++){int x;  cin>>x;v[n].push_back({x,i});//第n层一共n人}for(int i=n;i>0;i--){int len=pow(2,i);for(int j=0;j<len;j+=2){//两两比较找到胜者，晋级到上一层if(v[i][j].fi>v[i][j+1].fi)v[i-1].push_back({v[i][j].fi,v[i][j].se});elsev[i-1].push_back({v[i][j+1].fi,v[i][j+1].se});}}/*for(int i=n;i>0;i--){int len=pow(2,n);for(int j=0;j<v[i].size();j++){cout<<v[i][j].fi<<' ';}cout<<endl;}*/if(v[1][0].fi>v[1][1].fi)//这层存的是冠军和亚军，找到较小者为亚军cout<<v[1][1].se<<endl;elsecout<<v[1][0].se<<endl;
}signed main(){IOS;int T=1;while(T--){solve();}return 0;
}

【深基16.例3】二叉树深度

题目描述

有一个 $n(n\le 10^6)$ 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 $n$），建立一棵二叉树（根节点的编号为 $1$），如果是叶子结点，则输入 0 0。

建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。

输入格式

第一行一个整数 $n$，表示结点数。

之后 $n$ 行，第 $i$ 行两个整数 $l$、$r$，分别表示结点 $i$ 的左右子结点编号。若 $l=0$ 则表示无左子结点，$r=0$ 同理。

输出格式

一个整数，表示最大结点深度。

样例 #1

样例输入 #1

7
2 7
3 6
4 5
0 0
0 0
0 0
0 0

样例输出 #1

4

基本思路：

• 一道求二叉树深度的题，可以用dfs或者bfs求每个节点的深度，详细请看代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 1000010;
struct Node{int l,r;int depth; 
}tree[N];
int n,maxdepth;//dfs求深度
inline void dfs(int x){if(tree[x].l){tree[tree[x].l].depth=tree[x].depth+1;maxdepth=max(maxdepth,tree[tree[x].l].depth);dfs(tree[x].l);}if(tree[x].r){tree[tree[x].r].depth=tree[x].depth+1;maxdepth=max(maxdepth,tree[tree[x].r].depth);dfs(tree[x].r);}
}void solve(){cin>>n;for(int i=1;i<=n;i++){int x,y; cin>>x>>y;if(x)tree[i].l=x;if(y)tree[i].r=y;}//一 dfs求深度//tree[1].depth=1;//dfs(1);//二 或者bfs求深度queue<Node> q;tree[1].depth=1;q.push(tree[1]);while(!q.empty()){auto t=q.front();q.pop();if(t.l){//左子树存在tree[t.l].depth=t.depth+1;//左儿子的深度等于当前节点深度+1maxdepth=max(maxdepth,tree[t.l].depth);//找到深度的最大值q.push(tree[t.l]);} if(t.r){//右子树存在tree[t.r].depth=t.depth+1;maxdepth=max(maxdepth,tree[t.r].depth);q.push(tree[t.r]);}}
//	for(int i=1;i<=7;i++)
//	  cout<<tree[i].depth<<' ';cout<<maxdepth<<endl;
}signed main(){IOS;int T=1;while(T--){solve();}return 0;
}

[USACO3.4] 美国血统 American Heritage

题目描述

农夫约翰非常认真地对待他的奶牛们的血统。然而他不是一个真正优秀的记帐员。他把他的奶牛 们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”和“树的前序遍历”的符号加以记录而 不是用图形的方法。

你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，创建奶牛家谱的“树的 后序遍历”的符号。每一头奶牛的姓名被译为一个唯一的字母。（你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）显然，这里的树不会有多于 $26$ 个的顶点。

这是在样例输入和样例输出中的树的图形表达方式：

　　　　　　　　 C/  \/　　\B　　  G/ \　　/A   D  H/ \E   F

附注：

• 树的中序遍历是按照左子树，根，右子树的顺序访问节点；
• 树的前序遍历是按照根，左子树，右子树的顺序访问节点；
• 树的后序遍历是按照左子树，右子树，根的顺序访问节点。

输入格式

第一行一个字符串，表示该树的中序遍历。

第二行一个字符串，表示该树的前序遍历。

输出格式

单独的一行表示该树的后序遍历。

样例 #1

样例输入 #1

ABEDFCHG
CBADEFGH

样例输出 #1

AEFDBHGC

提示

题目翻译来自NOCOW。

USACO Training Section 3.4

基本思路：

• 给出先序遍历和中序遍历求后序遍历：
• （1）我们知道先序遍历最后一个节点为根节点，找到这个根节点在中序遍历中的位置i。
• （2）i的左边即为该根节点的左子树，右边即为右子树。此时通过分析中序遍历找到左子树的大小，再次确定左子树中根节点的位置，右子树同理。
• （3）继续重复步骤1、2，不断递归即可。

题目中要求后序遍历，在建树中输出即可求得。求后序遍历的话画图分析就清晰多了ヾ(≧▽≦*)o

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define gcd __gcd
#define repn(i,a,n) for(int i = a; i <= n; i++)
#define rep(i,a,n) for(int i = a; i < n; i++)
typedef pair<int,int> PII; 
const int N = 27;
string pre,mid;//存放前序遍历和中序遍历 
int n;//二叉树节点个数 void build_tree(int lp,int rp,int lm,int rm){//前序左边界右边界、中序左边界有边界 if(lp>rp) return;//越界了 char root=pre[lp];//找到根节点，前序：根左右 //需要找到根节点root在中序的位置 //通过根节点找到左子树和右子树int i=lm;//i即为分界线 while(mid[i]!=root&&i<=rm)i++;build_tree(lp+1,lp+(i-lm),lm,i-1); //左子树build_tree(lp+(i-lm)+1,rp,i+1,rm);//右子树..cout<<root;//左右根，此时不断输出即为后序遍历 
}void solve(){cin>>mid>>pre;//中序、前序 n=mid.size();//字符串长度 mid=" "+mid,pre=" "+pre; build_tree(1,n,1,n);//前序1-n,中序1-n 
}signed main(){IOS;int T=1;while(T--){solve();}return 0;
}