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 }
?
?
的區別)
)
)
)
)
