平衡二叉樹判斷

平衡二叉樹的定義：（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);
}