首页 > 代码库 > ZOJ3805Machine(二叉树左右子树变换)
ZOJ3805Machine(二叉树左右子树变换)
1 /* 2 题意：建立一棵二叉树，左子树和父节点占一个宽度，右子树另外占一个宽度！ 3 使任意左右子树交换顺序，使得整个树的宽度最小！ 4 思路：递归交换左右子树 ！
开始写的代码复杂了，其实左右子树不用真的交换，只要返回交换与不交换最小的宽度值就好了，下次不用在查询了！ 5 */ 6 #include<iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm>10 #define N 1000511 using namespace std;12 13 int tree[N][2];14 int link[N];15 int n;16 17 int dfs(int cur){18 if(cur==0) return 0;19 int aR=1+dfs(tree[cur][1]);//右子树的宽度 20 int aL=dfs(tree[cur][0]);//左子树的宽度 21 return min(max(aR-1, aL+1), max(aR, aL));//aR-1是右子树变成左子树后的宽度，aL是左子树变成右子树的宽度 22 }23 24 int main(){25 while(scanf("%d", &n)!=EOF){26 memset(tree, 0, sizeof(tree));27 memset(link, 0, sizeof(link));28 for(int i=1; i<n; ++i){29 int u;30 scanf("%d", &u);31 if(link[u]==0){ 32 link[u]=1;33 tree[u][0]=i+1;34 } 35 else {36 tree[u][1]=i+1;37 } 38 }39 printf("%d\n", dfs(1));40 }41 return 0;42 }
1 //这个就是写复杂了，但是很庆幸的过了！ 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define N 10005 7 using namespace std; 8 9 int tree[N][2];10 int link[N];11 int n, wide;12 13 int dfs(int cur){14 if(cur==0) return 0;15 int aR=1+dfs(tree[cur][1]);16 int aL=dfs(tree[cur][0]);17 return max(aL, aR);18 }19 20 void updateT(int cur){21 if(cur==0) return;22 updateT(tree[cur][0]);23 updateT(tree[cur][1]);24 int aL, aR;25 aL=dfs(tree[cur][0]);26 aR=1+dfs(tree[cur][1]);27 if(cur==1) wide=min(max(aR-1, aL+1), max(aR, aL));28 if(aR-aL>1){29 int tmp=tree[cur][1];30 tree[cur][1]=tree[cur][0];31 tree[cur][0]=tmp;32 }33 }34 35 int main(){36 while(scanf("%d", &n)!=EOF){37 memset(tree, 0, sizeof(tree));38 memset(link, 0, sizeof(link));39 for(int i=1; i<n; ++i){40 int u;41 scanf("%d", &u);42 if(link[u]==0){ 43 link[u]=1;44 tree[u][0]=i+1;45 } 46 else {47 tree[u][1]=i+1;48 } 49 }50 updateT(1);51 printf("%d\n", wide);52 }53 return 0;54 }
ZOJ3805Machine(二叉树左右子树变换)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。