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 参数传递法：
[cpp]
bool isBalanced(TreeNode *root) {
if(!root) return true;
bool balance = true;
balanceHelper(root, balance);
return balance;
}
void treeHeight(TreeNode *node, int &h, int oneh = 0)
{
if(!node) return;
oneh++;
treeHeight(node->left, h, oneh);
treeHeight(node->right, h, oneh);
if(!node->left && !node->right)
h = oneh > h oneh:h;
}
void balanceHelper(TreeNode *node, bool &balance)
{
if(!balance || !node) return;
int lh = 0;
int rh = 0;
treeHeight(node->left, lh);
treeHeight(node->right, rh);
if (abs(lh-rh) > 1)
{
balance = false;
return;
}
balanceHelper(node->left, balance);
balanceHelper(node->right, balance);
}
2 返回值：
[cpp]
bool isBalanced2(TreeNode *root) {
if (root == nullptr) return true;
int left = getHeight(root->left);
int right = getHeight(root->right);
if (abs(left - right) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
int getHeight(TreeNode *n) {
if (n == nullptr) return 0;
return max(getHeight(n->left), getHeight(n->right)) + 1;
}
3 加判断：
[cpp]
int cntHeight(TreeNode *root) {
if(root == NULL) return 0;
int l = cntHeight(root->left);
int r = cntHeight(root->right);
if(l < 0 || r < 0 || abs(l-r) > 1) return -1;
else return max(l, r) + 1;
}
bool isBalanced3(TreeNode *root) {
if(root == NULL) return true;
int l = cntHeight(root->left);
int r = cntHeight(root->right);
if(l < 0 || r < 0 || abs(l-r) > 1) return false;
else return true;
}
4 其实可以更加简单：
[cpp]
bool isBalanced5(TreeNode *root) {
return (height_(root) >= 0 );
//or: return cntHeight(root) >=0;
}
int height_(TreeNode *root){
if (root == NULL) return 0;
int lh = height_(root->left);
if (lh == -1 ) return lh;
int rh = height_(root->right);
if (rh == -1 ) return rh;
int d = rh - lh;
if (d > 1 || d < -1) return -1;
else return 1 + ( d > 0 rh : lh );
}
5 或者：
[cpp]
bool isBalanced(TreeNode *root) {
return height(root) != -1;
}
int height(TreeNode *root)
{
if(root == nullptr)
return 0;
int leftHeight = height(root->left);
if(leftHeight == -1)
return -1;
int rightHeight = height(root->right);
if(rightHeight == -1)
return -1;
if(abs(leftHeight - rightHeight) > 1)
return -1;
return 1 + max(leftHeight, rightHeight);
}
6 还有：
[cpp]
bool f(TreeNode *root, int &d) {
if (!root) {
d = 0;
return true;
}
int ld, rd;
bool lb = f(root->left, ld);
bool rb = f(root->right, rd);
d = ld > rd ld+1:rd+1;
if (abs(ld-rd)>1) return false;
return lb && rb;
}
boo