Given a 红黑树,我需要写一个高效算法检查对于每个节点,从该节点到后代叶子的所有路径是否包含相同数量的黑色节点,即如果属性为 true 或 false,则算法应返回布尔值。
它将返回 RB 树的黑色高度。如果高度为0,则该树是无效的红黑树。
int BlackHeight(NodePtr root)
{
if (root == NULL)
return 1;
int leftBlackHeight = BlackHeight(root->left);
if (leftBlackHeight == 0)
return leftBlackHeight;
int rightBlackHeight = BlackHeight(root->right);
if (rightBlackHeight == 0)
return rightBlackHeight;
if (leftBlackHeight != rightBlackHeight)
return 0;
else
return leftBlackHeight + root->IsBlack() ? 1 : 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)