平衡二叉樹判斷

平衡二叉樹的定義：（1）必須是二叉樹（可以是空樹）；（2）它的左右子樹也應該是平衡二叉樹，且左右子樹的深度之差的絕對值不能超過1.（即可以為0，1）

struct Node
{
int data;
Node *left;
Node *right;
};

以上為節點的結構。題目：現需要設計一個函數來判斷給定的二叉樹是否為平衡二叉樹。【給定二叉樹的根節點為R】

（1）依據平衡二叉樹的定義來判斷，即需要求設計一個求取樹深度的函數

int Deepth(Node *R)
{
if(!R)
return 0;
else
{
int left_deep = Deepth(R->left);
int right_deep = Deepth(R->right);
return 1+((left_deep>=right_deep)?left_deep:right_deep);
}
}

bool IsBiTree(Node *R)
{
if(!R)
return true;
int left_deep = Deepth(R->left);
int right_deep=Deepth(R->right);
if(abs(left_deep - right_deep)>1)
return false;
else
return IsBiTree(R->left)&&IsBiTree(R->Right);
}

（2）直接遞歸判斷方法。[寫得風格有點糟糕，但願思路沒錯]

bool IsBiTree(Node *R)
{
if(!R)
return true;
if(R->left==NULL && R->right==NULL)
return true;
else if(R->left==NULL && R->right->right==NULL)
return true;
else if(R->right==NULL && R->left->left==NULL)//前三種情況均是平衡二叉樹結束的情況
return true;
else if(R->left==NULL && R->right->right)
return false;
else if(R->right==NULL && R->left->left)
return false;
else
return IsBiTree(R->left)&&IsBiTree(R->right);
}