[3]輸入一顆二叉樹判斷是不是平衡二叉樹

題目：輸入一顆二叉樹的根結點，判斷該二叉樹是不是平衡二叉樹。平衡二叉樹是滿足所有結點的左右子樹的高度差不超過1的二叉樹

方案一：遍歷數組的每一個結點，對每一個結點求它的左右子樹的高度並進行判斷。時間復雜度大於O(n)，小於O(n^2)效率較低，因為有很多點需要重復訪問。

//二叉樹的結點
struct BinaryTreeNode{
     int m_value;
     BinaryTreeNode *m_lson;
     BinaryTreeNode *m_rson;
};

//求二叉樹的深度
int GetDepth(BinaryTreeNode *root){
	if(root == NULL){
	   return 0;
	}
	int lsonDepth = GetDepth(root->m_lson);
	int rsonDepth = GetDepth(root->m_rson);
	return lsonDepth < rsonDepth ? (rsonDepth+1) : (lsonDepth+1);
}

//方案一對每個結點進行判斷
bool IsBalanced(BinaryTreeNode *root){
	if(root == NULL){
	    return true;
	}
	int lsonDepth = GetDepth(root->m_lson);
	int rsonDepth = GetDepth(root->m_rson);
	int dis = lsonDepth-rsonDepth;
	if((dis <= 1) && (dis >= -1)){
		return IsBalanced(root->m_lson) && IsBalanced(root->m_rson);
	}
	else{
	    return false;
	}
} 

方案二：利用二叉樹的後序遍歷，對於先訪問左右子樹，然後對每個根結點進行判斷，傳入一個高度的參數即可。時間復雜度為O(n)。

//二叉樹的結點
struct BinaryTreeNode{
     int m_value;
     BinaryTreeNode *m_lson;
     BinaryTreeNode *m_rson;
};

//後序遍歷判斷是不是平衡二叉樹
bool IsBalanced(BinaryTreeNode *root, int *depth){
	if(root == NULL){
	    *depth = 0;
	    return true;
	}
	int lsonDepth = 0;
	int rsonDepth = 0;
	if(IsBalanced(root->m_lson, &lsonDepth) 
		&& IsBalanced(root->m_rson, &rsonDepth)){
	    int dis = lsonDepth-rsonDepth;
		if((dis >= -1) && (dis <= 1)){
		    *depth = 1+(lsonDepth < rsonDepth ? rsonDepth : lsonDepth);
		    return true;
		}
		else{
		    return false;
		}
	}
	else{
	    return false;
	}
}