1.描述
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.
2.分析
先判斷左子樹和右子樹是否為平衡豆拨，然后判斷左右子樹的高度差是否小于等于1待讳。
3.代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isChildBalanced(struct TreeNode* root, int* height) {
if (NULL == root) {
*height = 0;
return true;
}
int leftHeight, rightHeight;
bool left = isChildBalanced(root->left, &leftHeight);
bool right = isChildBalanced(root->right, &rightHeight);
*height = leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
bool balance = leftHeight >= rightHeight ? leftHeight - rightHeight <= 1 : rightHeight - leftHeight <=1;
return balance & left & right;
}
bool isBalanced(struct TreeNode* root) {
if (NULL == root) return true;
int height;
return isChildBalanced(root, &height);
}
