Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

分析

平衡二叉树指每个节点的两个子数的高度相差不大于1，因此通过递归判断两个子节点的高度作比较，而且如果子节点不平衡的话，父节点也不平衡。因此递归函数中返回值-1代替该节点是否平衡，代码如下，已通过。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int treeHeight(struct TreeNode* root)//return -1 meads not balanced; return >=0 means height of root
{
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)
        return 1;
    int leftHeight=treeHeight(root->left);
    int rightHeight=treeHeight(root->right);
    //printf("%d %d %d\n",root->val,leftHeight,rightHeight);
    if(leftHeight==-1||rightHeight==-1)
        return -1;
    if(leftHeight-rightHeight>1||rightHeight-leftHeight>1)
        return -1;
    if(leftHeight<rightHeight)
        return rightHeight+1;
    else
        return leftHeight+1;
}
bool isBalanced(struct TreeNode* root) {
    if(treeHeight(root)==-1)
        return false;
    else
        return true;
}