1 /* 2 题意：建立一棵二叉树，左子树和父节点占一个宽度，右子树另外占一个宽度！ 3 使任意左右子树交换顺序，使得整个树的宽度最小！ 4 思路：递归交换左右子树 ！
开始写的代码复杂了，其实左右子树不用真的交换，只要返回交换与不交换最小的宽度值就好了，下次不用在查询了！ 5 */ 6 #include<iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<algorithm> 10 #define N 10005 11 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 }
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3933889.html，如需转载请自行联系原作者
