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

Soucula · 2018-4-30 01:54:23

如果一个二叉树的所有结点满足其左右子树的高度相差的绝对值不超过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);
}

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

1 个回复