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.
C Solution:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool recu(struct TreeNode *root, int *len) {
if (!root) {
*len = 0;
return true;
}
int left;
if (!recu(root->left, &left)) return false;
int right;
if (!recu(root->right, &right)) return false;
if (left - right < 2 && right - left < 2) {
*len = (left > right ? left : right) + 1;
return true;
}
return false;
}
bool isBalanced(struct TreeNode* root) {
int heigh;
return recu(root, &heigh);
}
Summary:
- height-balanced is not typical balance.
LeetCode: 110. Balanced Binary Tree
近期评论