怎样判断二叉树是否为平衡二叉树

论坛 期权论坛 期权     
灰暗路过006   2018-4-26 14:02   3328   1
分享到 :
0 人收藏

1 个回复

倒序浏览
2#
Soucula  2级吧友 | 2018-4-30 01:54:23 发帖IP地址来自
如果一个二叉树的所有结点满足其左右子树的高度相差的绝对值不超过1则为平衡二叉树。
int getTreeDeep(TreeNode *root)
{
if (root == NULL)
return 0;
int deepLeft = getTreeDeep(root->left);
int deepRight = getTreeDeep(root->right);
return deepLeft >= deepRight ? (deepLeft + 1) : (deepRight + 1);
}
bool isBalanceTree(TreeNode *root)
{
if (root == NULL)
return true;
if (abs(getTreeDeep(root->left) - getTreeDeep(root->right)) > 1)
return false;
return isBalanceTree(root->left) && isBalanceTree(root->right);
}
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP