本文详解 BST 中 parent_r 递归方法的常见逻辑错误，并提供修复后的完整实现，确保能准确返回目标节点的父节点值（如查找 20 时正确返回 12），避免因递归返回值处理不当导致始终返回 None。
本文详解 bst 中 `parent_r` 递归方法的常见逻辑错误，并提供修复后的完整实现，确保能准确返回目标节点的父节点值（如查找 20 时正确返回 12），避免因递归返回值处理不当导致始终返回 `none`。
在二叉搜索树（BST）中，查找某节点的父节点看似简单，但递归实现极易陷入逻辑陷阱。原代码的核心问题在于：未及时传播子树中已找到的父节点结果，且错误地将 parent 初始化为 None 后覆盖了递归调用的返回值；同时，对左右子节点存在性的判断（node._left is not None or node._right is not None）与值匹配逻辑耦合过紧，导致无法在叶节点父级精准捕获匹配。
修复后的 parent_r_aux 方法遵循清晰的递归契约：先深入左子树查找，若成功则立即返回；否则再查右子树；均失败后，才检查当前节点是否为待查键的直接父节点。关键改进包括：
- ✅ 每次递归调用后立即检查返回值，非空即返，保证结果逐层上浮；
- ✅ 移除冗余的 parent = None 初始化，避免覆盖有效结果；
- ✅ 使用 node._left and node._left._value == key 替代松散的 or 判断，确保安全访问 _value 属性；
- ✅ 直接返回 node（而非 node._value），符合方法注释中“返回父节点值”的语义（调用方可自行取 .value，增强灵活性）。
以下是修正后的完整方法实现：
def parent_r(self, key):
"""
Returns the value of the parent node in a BST given a key.
"""
assert self._root is not None, "Cannot locate a parent in an empty BST"
parent_node = self.parent_r_aux(self._root, key)
return parent_node._value if parent_node else None
def parent_r_aux(self, node, key):
if node is None:
return None
# 先尝试在左子树中找父节点
parent = self.parent_r_aux(node._left, key)
if parent is not None:
return parent
# 左子树没找到，再尝试右子树
parent = self.parent_r_aux(node._right, key)
if parent is not None:
return parent
# 当前节点的左或右子节点值等于 key，则当前节点即为所求父节点
if node._left and node._left._value == key:
return node
if node._right and node._right._value == key:
return node
return None
注意事项：
- 该实现不依赖 BST 的有序性，适用于任意二叉树的父节点查找（若需利用 BST 性质优化，可改用迭代+比较路径的方式，时间复杂度降至 O(h)）；
- 若 key 等于根节点值，按定义无父节点，应返回 None——本实现天然满足；
- 实际使用中建议增加类型校验（如 key 是否可比）及重复值处理说明（标准 BST 不允许重复键，故无需额外去重逻辑）。
经测试，对题目所给树结构：
22 / \ 12 30 / \ / \ 8 20 25 40
调用 bst.parent_r(20) 将正确返回 12，彻底解决原方法恒返 None 的问题。
