Python含重复值二叉树的节点父节点获取及删除实现问题

Great question—dealing with duplicate values in binary trees definitely adds a twist to standard operations like finding parents or removing nodes. Let's work through your problems step by step, starting with fixing the get_parent() method, then exploring a cleaner approach that avoids needing parent lookups entirely.

Fixing the get_parent() Method (Handling Duplicate Values) #

Your original code has two core issues that are causing unexpected behavior:

1. Matching by value instead of node reference: When you pass a value like -1, the method returns the first node with that value it encounters (your root node in this case), not the specific child node you're targeting.
2. Flawed recursive return logic: The original code returns the target node itself when it finds a value match, instead of traversing up to return its actual parent.

The fix is simple: pass the target node object instead of its value. Since each node is a unique object (even if values are duplicated), we can reliably identify the exact node we're looking for.

Here's a corrected get_parent() implementation:

def get_parent(self, root, target_node):
    if root is None or root == target_node:
        # Root has no parent, or the target is the root itself
        return None
    
    # Check if left child is the target
    if root.left == target_node:
        return root
    # Check if right child is the target
    if root.right == target_node:
        return root
    
    # Recursively search left subtree
    left_parent = self.get_parent(root.left, target_node)
    if left_parent is not None:
        return left_parent
    
    # Recursively search right subtree
    return self.get_parent(root.right, target_node)

Now adjust your call to pass the actual node instead of its value, and you'll get the correct parent:

target_node = tree.left_child(tree.root.right)
parent_node = tree.get_parent(tree.root, target_node)
print(parent_node.val)  # This will output 5 as expected!

Alternative: Remove Nodes Without Finding the Parent #

Looking up parent nodes adds unnecessary complexity, especially with duplicate values. A cleaner approach is to use a recursive removal method that returns the modified subtree root, eliminating the need to track parents entirely.

Your existing left_child() method is perfect for this—we'll use it to find the in-order successor when deleting a node with two children.

Here's the implementation:

def remove_node(self, root, target_node):
    if root is None:
        return None
    
    # If we've found the node to delete
    if root == target_node:
        # Case 1: Node has no children
        if root.left is None and root.right is None:
            return None
        # Case 2: Node has one child
        elif root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        # Case 3: Node has two children - replace with in-order successor
        else:
            min_right_node = self.left_child(root.right)
            # Copy the successor's value to the current node
            root.val = min_right_node.val
            # Delete the successor node from the right subtree
            root.right = self.remove_node(root.right, min_right_node)
            return root
    
    # Recursively update left and right subtrees
    root.left = self.remove_node(root.left, target_node)
    root.right = self.remove_node(root.right, target_node)
    
    return root

To use this, call it with your tree's root and the target node, then reassign the root (in case the root was the node being deleted):

target_node = tree.left_child(tree.root.right)
tree.root = tree.remove_node(tree.root, target_node)

If you need to remove all nodes with a specific value (instead of a single node), modify the method to traverse first and delete all matches:

def remove_by_value(self, root, target_val):
    if root is None:
        return None
    
    # First remove all matches from left and right subtrees
    root.left = self.remove_by_value(root.left, target_val)
    root.right = self.remove_by_value(root.right, target_val)
    
    # If current node matches the value, delete it
    if root.val == target_val:
        # Same three cases as before
        if root.left is None and root.right is None:
            return None
        elif root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        else:
            min_right_node = self.left_child(root.right)
            root.val = min_right_node.val
            root.right = self.remove_by_value(root.right, min_right_node.val)
            return root
    
    return root

Call this to delete all nodes with value -1:

tree.root = tree.remove_by_value(tree.root, -1)

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