ZOJ3805Machine(二叉树左右子树变换)

时间:2023-03-08 17:14:35
 /*
题意:建立一棵二叉树,左子树和父节点占一个宽度,右子树另外占一个宽度!
使任意左右子树交换顺序,使得整个树的宽度最小!
思路:递归交换左右子树 !
开始写的代码复杂了,其实左右子树不用真的交换,只要返回交换与不交换最小的宽度值就好了,下次不用在查询了!
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
using namespace std; int tree[N][];
int link[N];
int n; int dfs(int cur){
if(cur==) return ;
int aR=+dfs(tree[cur][]);//右子树的宽度
int aL=dfs(tree[cur][]);//左子树的宽度
return min(max(aR-, aL+), max(aR, aL));//aR-1是右子树变成左子树后的宽度,aL是左子树变成右子树的宽度
} int main(){
while(scanf("%d", &n)!=EOF){
memset(tree, , sizeof(tree));
memset(link, , sizeof(link));
for(int i=; i<n; ++i){
int u;
scanf("%d", &u);
if(link[u]==){
link[u]=;
tree[u][]=i+;
}
else {
tree[u][]=i+;
}
}
printf("%d\n", dfs());
}
return ;
}
 //这个就是写复杂了,但是很庆幸的过了!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
using namespace std; int tree[N][];
int link[N];
int n, wide; int dfs(int cur){
if(cur==) return ;
int aR=+dfs(tree[cur][]);
int aL=dfs(tree[cur][]);
return max(aL, aR);
} void updateT(int cur){
if(cur==) return;
updateT(tree[cur][]);
updateT(tree[cur][]);
int aL, aR;
aL=dfs(tree[cur][]);
aR=+dfs(tree[cur][]);
if(cur==) wide=min(max(aR-, aL+), max(aR, aL));
if(aR-aL>){
int tmp=tree[cur][];
tree[cur][]=tree[cur][];
tree[cur][]=tmp;
}
} int main(){
while(scanf("%d", &n)!=EOF){
memset(tree, , sizeof(tree));
memset(link, , sizeof(link));
for(int i=; i<n; ++i){
int u;
scanf("%d", &u);
if(link[u]==){
link[u]=;
tree[u][]=i+;
}
else {
tree[u][]=i+;
}
}
updateT();
printf("%d\n", wide);
}
return ;
}