描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

注：我们约定空树是平衡二叉树。

//方法1：自顶向下
/*
    求出以每个结点为根的树的高度，然后再根据左右子树高度差绝对值小于等于1，,就可以判断以每个结点为根的树是否满足定义。
    
*/

int num_tree(TreeNode* root)
{
	if(root==NULL)
	{
		return 0;
	}
	int left_num=num_tree(root->left)+1;
	int right_num=num_tree(root->right)+1;
	return left_num>right_num?left_num:right_num;
	
}

bool IsBalanced_Solution(TreeNode* pRoot) 
{
	if(pRoot==NULL)
		return true;
	
	int lnum=num_tree(pRoot->left);
	int rnum=num_tree(pRoot->right);
	if(abs(lnum-rnum)>1)//取绝对值函数 
		return false;
		
	return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right); 
   
}

//方法2：自底向上
/*
    采用后序遍历的方式遍历二叉树的每一个节点，在遍历到一个节点之前我们就已经遍历了它的左右字数。
    
    此时，记录每个节点为根节点的树的高度，就可以一边遍历一边判断每个节点是不是平衡的。

*/

bool IsBalance(TreeNode* root,int* depth)
{
	if(root==NULL)
	{
		*depth=0;
		return true;
	}
	int left_dep,right_dep;
	bool left_balance=IsBalance(root->left,&left_dep);//先判断左子树 
	bool right_balance=IsBalance(root->right,&right_dep);//再判断右子树 
	if(left_balance&&right_balance)
	{
		if(abs(left_dep-right_dep)<=1)
		{
			*depth=max(left_dep,right_dep)+1;//最后加上根节点的深度 
			return true;
		}
	}
	return false;
	
}


bool IsBalanced_Solution(TreeNode* pRoot) 
{
	int dep=0;//用来保存树的深度 
	return IsBalance(pRoot,&dep);//引用传递 
   
}