二叉搜索树(BST)父节点查找函数返回None问题求助

你的递归函数存在两个核心问题，导致无法正确返回目标节点的父节点值：

1. 递归结果未向上传递 #

在parent_r_aux中，你递归调用了左、右子树，但没有将子递归返回的有效父节点值传递到上层。比如递归到节点12的层级时，明明已经计算出parent = 12，但这个值无法传递到更高层的调用中——因为你没有处理子递归返回的lparent和rparent，深层找到的结果被直接丢弃，最终只能返回当前层级计算的parent（多数情况为None）。

2. 空节点属性访问风险 #

在判断node._left._value == key or node._right._value == key时，没有先确认子节点是否存在。比如当节点没有右子节点时，node._right是None，直接访问_value会触发AttributeError。

修复后的代码 #

def parent_r(self, key):
    """
    ---------------------------------------------------------
    Returns the value of the parent node in a bst given a key.
    ---------------------------------------------------------
    Parameters:
        key - a key value (?)
    Returns:
        value - a copy of the value in a node that is the parent of the
        key node, None if the key is not found.
    ---------------------------------------------------------
    """
    assert self._root is not None, "Cannot locate a parent in an empty BST"
    # 根节点无父节点，直接返回None
    if self._root._value == key:
        return None
    return self.parent_r_aux(self._root, key)

def parent_r_aux(self, node, key):
    if node is None:
        return None

    # 先检查当前节点是否是目标节点的父节点
    left_match = node._left is not None and node._left._value == key
    right_match = node._right is not None and node._right._value == key
    if left_match or right_match:
        return node._value
    
    # 利用BST特性优化搜索：小于当前节点值搜左子树，否则搜右子树
    if key < node._value:
        return self.parent_r_aux(node._left, key)
    else:
        return self.parent_r_aux(node._right, key)

修复说明 #

• 增加根节点特殊判断：如果目标key是根节点的值，直接返回None（根节点无父节点）。
• 优先检查当前节点是否为目标节点的父节点，符合条件则直接返回当前节点值。
• 利用BST特性减少无效遍历：根据key与当前节点值的大小关系，只搜索对应子树，提升效率。
• 修复空节点访问问题：先判断子节点是否存在，再访问其_value属性。
• 递归调用后直接返回子递归结果，确保找到的父节点值能向上传递到顶层调用。

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