红黑树验证：如何实现叶子到根的黑节点数量一致性检查？

嘿，这个问题我当初写红黑树校验逻辑的时候也踩过坑！其实核心就是遍历所有从根到空节点的路径，记录每条路径的黑节点数，确保它们完全相等。下面给你拆解具体怎么做：

核心思路 #

红黑树的第4条特性要求所有从根到空叶子（把空节点当作黑色叶子）的路径，黑节点数量必须一致。我们可以用递归遍历的方式，跟踪当前路径的黑节点计数，同时用一个基准值来对比所有路径的计数。

具体实现步骤 #

1. 初始化基准值：用一个可变的变量（比如列表、引用类型）来保存第一条有效路径的黑节点数，初始可以设为一个特殊值（比如-1）表示还未确定基准。
2. 递归遍历节点：
   • 当遇到空节点时：
     • 如果基准值还没设置，就把当前路径的黑节点数赋值给它；
     • 否则，对比当前计数和基准值，不等就直接返回false；
     • 相等的话返回true。
   • 当遇到非空节点时：
     • 如果当前节点是黑色，把当前路径的黑节点计数加1；
     • 递归检查左子树，左子树不满足就直接返回false；
     • 再递归检查右子树，右子树不满足也直接返回false；
     • 左右都没问题，返回true。

伪代码示例 #

这里用Python风格的伪代码给你演示：

def is_black_height_consistent(root):
    # 用列表存基准黑数，因为列表是可变对象，递归中能修改
    base_black_count = [-1]

    def traverse(node, current_count):
        # 空节点视为黑色叶子
        if node is None:
            if base_black_count[0] == -1:
                base_black_count[0] = current_count
            else:
                if current_count != base_black_count[0]:
                    return False
            return True
        
        # 当前节点是黑色，计数+1
        if node.color == "BLACK":
            current_count += 1
        
        # 先检查左子树，不满足直接返回
        if not traverse(node.left, current_count):
            return False
        # 再检查右子树
        if not traverse(node.right, current_count):
            return False
        
        return True

    return traverse(root, 0)

注意事项 #

• 如果你用的是哨兵NIL节点（很多红黑树实现会用专门的NIL节点代替null），把判断node is None改成node == NIL即可，逻辑完全一致；
• 这个方法是提前终止的，只要发现某条路径不符合，立刻返回结果，不用遍历完所有节点，效率很高；
• 别忘了，空节点本身要算黑色，所以遇到空节点时必须参与计数对比，这是很容易漏的点！

内容的提问来源于stack exchange，提问作者Adam Ralphus