题目描述：
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 左右两个子树的高度差的绝对值不超过 1
题目来源：leetcode
思路：每个子树的左右子树比较
nt maxDepth(struct TreeNode* root){
if(root == NULL)
return 0;
return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}
bool isBalanced(struct TreeNode* root){
if(root == NULL)
return true;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return abs(leftDepth-rightDepth) < 2
&& isBalanced(root->left)
&& isBalanced(root->right);
}
isBalanced递归—》N次
每次递归：–》N N/2 N/2 N/4 N/4…
（假设理想情况下是满二叉树)
时间复杂度：O(N^2)
进阶：时间复杂度为：O(N)
方法：后序遍历
bool _isBalanced(struct TreeNode* root,int* ph){
if(root == NULL)
{
*ph = 0;
return true;
}
//后序
//先判断左子树，再判断右子树
int leftHeight = 0;
if(_isBalanced(root->left,&leftHeight) == false)
return false;
int rightHeight = 0;
if(_isBalanced(root->right,&rightHeight) == false)
return false;
//同时再把当前高度带给上一层的父亲
*ph = fmax(leftHeight,rightHeight)+1;
return abs(leftHeight-rightHeight) < 2;
}
bool isBalanced(struct TreeNode* root){
int height = 0;
return _isBalanced(root,&height);
}
