Python二叉搜索树(BST)插入节点功能未生效的原因是什么？

你的putValueInBST无法正常插入节点，核心原因是Python的函数参数传递规则+没有将新建节点与父节点绑定，具体分析如下：

• 当递归到root is None的分支时，你执行的root = Node(val)只是给当前函数栈内的局部变量root赋值，该变量和上层递归中对应的root.right/root.left指针没有关联，函数执行结束后局部变量被回收，父节点的对应指针完全没有被修改，新节点自然没有挂载到BST树上。
• 你手动实现的put_val_manually能正常生效，是因为你直接修改了父节点对象的right属性，属于对已有对象的成员修改，而非对局部变量重新赋值，修改结果会保留在原对象上。

修复方案 #

方案1：递归返回节点指针，上层接收赋值（兼容性更好） #

这种写法可以兼容根节点为空的初始化场景：

def putValueInBST(root, val):
    # 当前位置为空，返回新建节点给上层父节点绑定
    if root is None:
        return Node(val)
    if val > root.data:
        # 右子树的插入结果赋值给root.right
        root.right = putValueInBST(root.right, val)
    else:
        # 左子树的插入结果赋值给root.left
        root.left = putValueInBST(root.left, val)
    return root

调用示例：

# 如果根节点可能为空，调用时接收返回值更新根节点
root = putValueInBST(root, 7)

方案2：提前判断子节点状态，直接操作父节点属性 #

如果可以保证调用时传入的根节点不为空，可以用这种写法：

def putValueInBST(root, val):
    if val > root.data:
        # 右子节点为空直接赋值，否则递归右子树
        if root.right is None:
            root.right = Node(val)
        else:
            putValueInBST(root.right, val)
    else:
        # 左子节点为空直接赋值，否则递归左子树
        if root.left is None:
            root.left = Node(val)
        else:
            putValueInBST(root.left, val)

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