二叉搜索树 - 父节点方法错误输出

Question

此函数在二叉搜索树中搜索键并返回等于键的节点的父节点。但由于某种原因，当我调用此函数时，我的输出仍然为 None。我的测试看起来像这样：

bst=

    22
   /  \
 12    30
/  \  /  \
8  20 25  40

b = bst.parent_r(20)
print(b)




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"

        parent = self.parent_r_aux(self._root, key)
        return parent

    def parent_r_aux(self, node, key):
        parent = None

        if node is None:
            return None

        lparent = self.parent_r_aux(node._left, key)
        if lparent is None:
            rparent = self.parent_r_aux(node._right, key)
        
        if node._left is not None or node._right is not None:
            if node._left._value == key or node._right._value == key:
                parent = node._value
return parent

根据我的测试，我期望获得节点值 12

Answer 1

您需要检查是否在递归调用中找到了值，如果是则返回。

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

    parent = self.parent_r_aux(node._left, key)
    if parent:
        return parent

    parent = self.parent_r_aux(node._right, key)
    if parent:
        return parent

    if node._left and node._left._value == key:
        return node
    if node._right and node._right._value == key:
        return node