判断二叉树是否为红绿树的递归实现问题咨询

First, let’s clear up the core gaps in your current implementation: it only checks immediate parent-child pairs and doesn’t recursively validate the entire subtree, plus the base case for None nodes wasn’t properly resolved. Here’s how to refine the logic:

Corrected checkTree Function #

def checkTree(node):
    # Base case: empty subtree is always valid (no rules to break)
    if node is None:
        return True
    
    # Check left child if it exists
    if node.left is not None:
        if node.color == node.left.color:
            return False
    
    # Check right child if it exists
    if node.right is not None:
        if node.color == node.right.color:
            return False
    
    # Recursively validate both left and right subtrees
    return checkTree(node.left) and checkTree(node.right)

Key Fixes Explained #

• Base Case Handling: When node is None, we return True because an empty subtree can’t violate the color rule—there’s nothing to check here. This is critical for terminating the recursion correctly.
• Simplified Child Checks: Instead of splitting into "1 child" or "2 children" cases, we check each child individually. This covers all scenarios (0, 1, or 2 children) cleanly without redundant logic.
• Full Subtree Validation: After confirming the current node’s immediate children are valid, we need to ensure all descendant nodes follow the rule too. We do this by recursively checking both subtrees and returning the logical AND of their results—if either subtree is invalid, the whole tree is invalid.

How It Runs #

For any non-null node:

1. We first verify its left child (if present) has a different color. If not, return False right away.
2. Repeat the check for the right child.
3. Finally, recursively validate both subtrees. Only if both subtrees pass does the function return True.

This approach ensures every parent-child pair in the entire tree is checked, not just the top-level ones.

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