algorithm - 如何检查节点到其后代叶子的所有路径的黑色高度？

给定一棵红黑树，我需要编写一个有效的算法，检查每个节点从节点到后代叶的所有路径是否包含相同数量的黑色节点，即如果属性为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;
}