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.
分析
平衡二叉樹指每個節(jié)點的兩個子數(shù)的高度相差不大于1，因此通過遞歸判斷兩個子節(jié)點的高度作比較缰犁，而且如果子節(jié)點不平衡的話，父節(jié)點也不平衡。因此遞歸函數(shù)中返回值-1代替該節(jié)點是否平衡锦茁，代碼如下侥啤，已通過沾谓。
/**
* 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;
}
