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;
}
