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，从而不必遍历整棵树
源码
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#define max(A,B) ((A)>(B)?(A):(B))
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int height(struct TreeNode *root) {
if(root == NULL)
return 0;
int left_height = height(root->left);
if(left_height == -1)
return -1;
int right_height = height(root->right);
if(right_height == -1)
return -1;
if(abs(left_height-right_height) > 1)
return -1;
return max(left_height, right_height)+1;
}
int isBalanced(struct TreeNode *root) {
if(root == NULL)
return 1;
return height(root) >= 0;
}
int main() {
struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = 5;
struct TreeNode *left1_1 = malloc(sizeof(struct TreeNode));
left1_1->val = 3;
struct TreeNode *left2_1 = malloc(sizeof(struct TreeNode));
left2_1->val = 1;
root->left = left1_1;
root->right = NULL;
left1_1->left = left2_1;
left1_1->right = NULL;
left2_1->left = NULL;
left2_1->right = NULL;
assert(isBalanced(root) == 0);
return 0;
}
