題目來源:
http://zhedahht.blog.163.com/blog/static/25411174201142733927831/
題目：輸入一棵二叉樹的根結(jié)點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結(jié)點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX(a, b) ((a)>(b) ? (a) : (b))
#define ABS(x) ((x)>=0 ? (x) : ((x)*(-1)))
struct Node {
void *data;
struct Node *left, *right;
};
int
depth(struct Node *root)
{
if(root == NULL)
return 0;
int ldepth = depth(root->left);
int rdepth = depth(root->right);
return MAX(ldepth, rdepth) + 1;
}
int
btree_isbalanced_naive(struct Node *root) /* return 1 if balanced, or return 0 */
{
if(root == NULL)
return 1;
int ldepth = depth(root->left);
int rdepth = depth(root->right);
int diff = ldepth - rdepth;
if(ABS(diff) > 1)
return 0;
return (btree_isbalanced_naive(root->left) && btree_isbalanced_naive(root->right));
}
int
btree_isbalanced(struct Node *root, int *depth)
{
if(root == NULL) {
*depth = 0;
return 1;
}
int ldepth, rdepth, diff;
if(!btree_isbalanced(root->left, &ldepth) || !btree_isbalanced(root->right, &rdepth))
return 0;
*depth = MAX(ldepth, rdepth) + 1;
diff = ldepth - rdepth;
return (ABS(diff)<=1 ? 1 : 0);
}
int
main(int argc, char **argv)
{
struct Node a = {NULL, NULL, NULL};
struct Node b = {NULL, NULL, NULL};
struct Node c = {NULL, NULL ,NULL};
struct Node d = {NULL, &b, NULL};
struct Node e = {NULL, &a, &d};
struct Node f = {NULL, NULL, NULL};
struct Node g = {NULL, &e, &f};
int ret1 = btree_isbalanced_naive(&g);
printf("%s\n", ret1 ? "YES" : "NO");
int dpth = 0;
int ret2 = btree_isbalanced(&g, &dpth);
printf("%s : %d\n", ret2 ? "YES" : "NO", dpth);
return 0;
}