UVA839

這道題又是一道遞歸的題目

先貼上代碼

//這種沒有明確說個數的動態分配還是得用new
#include<cstdio>
#include<iostream>
using namespace std;
struct mobile
{int WL,DL,WR,DR;mobile *left,*right;mobile(mobile *a=NULL,mobile*b=NULL):left(a),right(b){}
};
mobile *top =NULL;
int kase;mobile* read_input()
{mobile *u = new mobile;scanf("%d%d%d%d",&u->WL,&u->DL,&u->WR,&u->DR);
//printf("%d %d %d %d \n",u->WL,u->DL,u->WR,u->DR);if(u->WL == 0){u->left = read_input();}if(u->WR == 0){u->right = read_input();}return u;
}
void clear(mobile* u)
{if(u){clear(u->left);clear(u->right);delete u;}
}//又是一個遞歸
void compute(mobile* u,int &W,bool &flag)
{//實際上這里應該有一個專門處理子節點的語句來結束遞歸，但是這個語句與下面的合并的語句可以和在一起判斷。if(u->WL&&u->WR){W = u->WL + u->WR;if(u->DL*u->WL==u->DR*u->WR){flag = true;}elseflag = false;return;}bool left_flag = 1;bool right_flag = 1;if((u->left) && (u->WL == 0))compute(u->left,u->WL,left_flag);if((u->right) && (u->WR == 0))compute(u->right,u->WR,right_flag);W = u->WL + u->WR;if(u->DL * u->WL == u->DR*u->WR&&left_flag&&right_flag){flag=true;}elseflag=false;return ;
}
void print_mobile(mobile *u)
{printf("\n");printf("%d %d %d %d \n",u->WL,u->DL,u->WR,u->DR);if(u->left)print_mobile(u->left);if(u->right)print_mobile(u->right);printf("\n");
}
int main()
{
#ifdef localfreopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endifscanf("%d",&kase);for(int i = 0;i < kase;i++){if(i)printf("\n");clear(top);top = read_input();
//print_mobile(top);bool flag ;int weight;compute(top,weight,flag);
//print_mobile(top);if(flag)printf("YES\n");elseprintf("NO\n");}return 0;
}

我的版本和劉汝佳版本有一點不一樣，劉汝佳是直接在輸入的時候就判斷完畢了，而我是輸入完之后又遍歷一遍才輸入完畢，在考場時傾向于后者，因為編程簡單

?

第二點是劉汝佳的bool數據結構是使用返回值來返回的，而我的是使用引用來修改的，這兩者在使用上沒有本質上的區別

?

第三點，在我寫的compute函數中，第一個部分處理葉節點的部分可以不要，因為可以后后面結合的部分合并起來，功能上是一樣的。

?

還是得細細品味這種遞歸的思想啊