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

/*
    题意：建立一棵二叉树，左子树和父节点占一个宽度，右子树另外占一个宽度！
          使任意左右子树交换顺序，使得整个树的宽度最小！
    思路：递归交换左右子树 ！ 
       开始写的代码复杂了，其实左右子树不用真的交换，只要返回交换与不交换最小的宽度值就好了，下次不用在查询了！
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
using namespace std;

int tree[N][2];
int link[N];
int n;

int dfs(int cur){
   if(cur==0) return 0;
   int aR=1+dfs(tree[cur][1]);//右子树的宽度 
   int aL=dfs(tree[cur][0]);//左子树的宽度 
   return min(max(aR-1, aL+1), max(aR, aL));//aR-1是右子树变成左子树后的宽度，aL是左子树变成右子树的宽度 
}

int main(){
   while(scanf("%d", &n)!=EOF){
          memset(tree, 0, sizeof(tree));
          memset(link, 0, sizeof(link));
       for(int i=1; i<n; ++i){
          int u;
          scanf("%d", &u);
          if(link[u]==0){ 
              link[u]=1;
              tree[u][0]=i+1;
          } 
          else {
              tree[u][1]=i+1;
          }  
       }
       printf("%d\n", dfs(1));
   }
   return 0;
} 
//这个就是写复杂了，但是很庆幸的过了！ 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10005
using namespace std;

int tree[N][2];
int link[N];
int n, wide;

int dfs(int cur){
   if(cur==0) return 0;
   int aR=1+dfs(tree[cur][1]);
   int aL=dfs(tree[cur][0]);
   return max(aL, aR);
}

void updateT(int cur){
    if(cur==0) return;
    updateT(tree[cur][0]);
    updateT(tree[cur][1]);
    int aL, aR;
    aL=dfs(tree[cur][0]);
    aR=1+dfs(tree[cur][1]);
    if(cur==1)  wide=min(max(aR-1, aL+1), max(aR, aL));
    if(aR-aL>1){
        int tmp=tree[cur][1];
        tree[cur][1]=tree[cur][0];
        tree[cur][0]=tmp;
    }
}

int main(){
   while(scanf("%d", &n)!=EOF){
          memset(tree, 0, sizeof(tree));
          memset(link, 0, sizeof(link));
       for(int i=1; i<n; ++i){
          int u;
          scanf("%d", &u);
          if(link[u]==0){ 
              link[u]=1;
              tree[u][0]=i+1;
          } 
          else {
              tree[u][1]=i+1;
          }  
       }
       updateT(1);
       printf("%d\n", wide);
   }
   return 0;
}