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

 /*

     题意：建立一棵二叉树，左子树和父节点占一个宽度，右子树另外占一个宽度！

           使任意左右子树交换顺序，使得整个树的宽度最小！

     思路：递归交换左右子树 ！ 
       开始写的代码复杂了，其实左右子树不用真的交换，只要返回交换与不交换最小的宽度值就好了，下次不用在查询了！

 */

 #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 ;

 }