BZOJ 1149 CTSC2007 風玲Mobiles DFS

題目大意：給定一棵完全二叉樹，可以交換某個節點的左右兒子，求最少交換多少次可以使所有的葉節點深度相差不超過1,且深度較大的葉節點都在深度較小的葉節點左側

鈴抄千

這水題居然還WA了兩次- - 腦殘害死人啊QAQ

首先DFS一次處理出深度最大和最小的葉節點 如果深度相差>=2則無解

然後再DFS一遍，對於每個節點首先向子節點遞歸，然後記錄左右兩棵子樹中深度較大葉節點的存在性和深度較小葉節點的存在性

如果兩棵子樹中都存在深度較大的葉節點和深度較小的葉節點則無解

否則討論一下是否需要交換 如果需要交換則ans++

最後輸出答案就行了- -

#include 
#include 
#include 
#include 
#define M 100100
using namespace std;
const int a[4][4]={
	{0,0,0,0},
	{0,0,0,0},
	{0,1,0,1},
	{0,1,0,0}
};
int n,ans,max_dpt,min_dpt=0x3f3f3f3f;
int ls[M],rs[M];

void DFS(int x,int dpt)
{
	if(x==-1)
	{
		max_dpt=max(max_dpt,dpt);
		min_dpt=min(min_dpt,dpt);
		return ;
	}
	DFS(ls[x],dpt+1);
	DFS(rs[x],dpt+1);
}
int Tree_DP(int x,int dpt)
{
	if(x==-1)
		return dpt==min_dpt?2:1;
	int l=Tree_DP(ls[x],dpt+1);
	int r=Tree_DP(rs[x],dpt+1);
	if(l==3&&r==3)
	{
		cout<<-1<>n;
	for(i=1;i<=n;i++)
		scanf("%d%d",&ls[i],&rs[i]);
	DFS(1,1);
	if(max_dpt-min_dpt>=2)
		return cout<<-1<