本文详解 BST 中 parent_r 方法的常见逻辑错误，指出原实现未正确传播递归结果的问题，并提供修复后的完整递归方案，确保能准确返回目标键值节点的父节点（而非 None）。
本文详解 bst 中 `parent_r` 方法的常见逻辑错误，指出原实现未正确传播递归结果的问题，并提供修复后的完整递归方案，确保能准确返回目标键值节点的父节点（而非 `none`）。
在二叉搜索树（BST）中，查找某节点的父节点是一个基础但易出错的操作。原始代码中 parent_r_aux 方法存在两个关键缺陷：
- 忽略递归调用的返回值：左、右子树递归调用后未检查是否已找到父节点，而是继续执行后续逻辑；
- 空指针风险与逻辑错位：node._left._value == key 前未确保 node._left is not None（虽有 or node._right is not None 判断，但该条件本身不保证左右子节点非空），且 parent = node._value 返回的是值而非节点引用，与函数注释中“返回 parent node”语义不符（实际应返回父节点对象，便于后续操作）。
以下是修正后的专业实现（保持原有接口语义，返回父节点对象，便于扩展）：
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 is not None and node._left._value == key:
return node
if node._right is not None and node._right._value == key:
return node
return None # 本节点及其子树均未命中
✅ 关键改进说明：
- 使用 if parent is not None: 显式判断并立即返回，避免无效遍历；
- 每次比较 node._left._value 前严格校验 node._left is not None，杜绝 AttributeError；
- 统一返回父节点对象（node），而非其 _value —— 这既符合方法签名中“returns the parent of the node”的设计意图，也便于上层调用方进一步访问父节点的其他属性（如高度、颜色等）；
- 时间复杂度仍为 O(h)，其中 h 为树高；最坏情况 O(n)（退化为链表），空间复杂度 O(h)（递归栈深度）。
⚠️ 注意事项：
- 若需支持重复键值（BST 通常不允许，但某些变体允许），此实现仅返回首个匹配父节点；
- 调用前务必确保 self._root is not None（由主方法 parent_r 中的 assert 保障）；
- 若目标 key 等于根节点值（即无父节点），按题设要求应返回 None —— 本实现天然满足（根节点无父，且不会被任一子节点匹配触发返回）。
通过上述重构，对示例树：
22 / \ 12 30 / \ / \ 8 20 25 40
执行 bst.parent_r(20) 将正确返回值为 12 的节点对象（即 node._value == 12），彻底解决原输出恒为 None 的问题。
