二叉搜索树(BST)节点兄弟判断递归方法故障排查求助

原代码的核心问题 #

1. 递归调用未返回结果：在递归进入左/右子树时，仅调用了sibling(T.right, k)和sibling(T.left, k)，但未用return传递递归结果，导致深层节点的判断结果无法向上反馈，最终返回None。
2. 逻辑冗余且错误：先通过T.find(k)拿到全局节点x，再判断x是否为当前树T的左右孩子——但递归到子树时，T是局部子树，x不可能是该子树的左右孩子（除非是子树根的直接子节点），这部分逻辑对深层节点完全无效。

修复方案 #

直接利用BST类中find方法的return_parent=True参数，一次性获取目标节点的父节点和自身节点，再通过父节点判断是否存在兄弟节点：

def sibling(T, k):
    # 利用find的return_parent参数，获取父节点和目标节点
    parent_node, target_node = T.find(k, return_parent=True)
    # 目标节点不存在，或是根节点（无父节点）时返回None
    if target_node is None or parent_node is None:
        return None
    # 判断目标节点是父节点的左/右孩子，返回另一个非空孩子的key
    if parent_node.left == target_node:
        return parent_node.right.key if not parent_node.right.is_empty else None
    else:
        return parent_node.left.key if not parent_node.left.is_empty else None

修复逻辑说明 #

1. 直接获取父节点：借助find(k, return_parent=True)跳过手动递归，直接拿到目标节点的父节点，避免原代码的递归传递漏洞。
2. 兄弟节点判断：
   • 若目标节点是父节点的左孩子，检查右孩子是否非空，非空则返回其key，否则返回None。
   • 若目标节点是父节点的右孩子，同理检查左孩子状态。
3. 边界处理：目标节点不存在或为根节点时，直接返回None。

验证结果 #

修复后执行将得到预期输出：

T = bst_list[3]
sibling(T,0): 3
sibling(T,1): None
sibling(T,2): None
sibling(T,3): 0
sibling(T,4): None
sibling(T,5): None
sibling(T,6): 8
sibling(T,7): 10
sibling(T,8): 6
sibling(T,9): 13

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