二叉搜索树插入函数空树用例失败：变量引用问题求助

问题场景 #

实现二叉搜索树的insertIntoBST函数时，最初的代码在大部分测试用例中正常，但当输入空树（root=None）时执行失败。将空树场景下的赋值对象从root改为temp后，代码恢复正常，以下是对原代码失败核心原因的解析。

最初代码（空树场景失败） #

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        temp = root
        prev_node = None
        while True:
            if not root:
                if prev_node is None:
                    root = TreeNode(val)
                elif val > prev_node.val:
                    prev_node.right = TreeNode(val)
                else:
                    prev_node.left = TreeNode(val)
                break
            elif val > root.val:
                prev_node = root
                root = root.right
            elif val < root.val:
                prev_node = root
                root = root.left
        return temp

修改后代码（正常运行） #

class Solution:
    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        temp = root
        prev_node = None
        while True:
            if not root:
                if prev_node is None:
                    temp = TreeNode(val)
                elif val > prev_node.val:
                    prev_node.right = TreeNode(val)
                else:
                    prev_node.left = TreeNode(val)
                break
            elif val > root.val:
                prev_node = root
                root = root.right
            elif val < root.val:
                prev_node = root
                root = root.left
        return temp

核心原因：Python的变量引用与赋值逻辑 #

在Python中，变量存储的是对象的引用，而非对象本身。原代码的问题出在空树场景下的赋值对象错误：

1. 当输入空树时，root初始为None，temp = root意味着temp和root都指向同一个None对象。
2. 在空树分支（prev_node is None）中，执行root = TreeNode(val)，这只是将函数内部的root变量重新指向了一个新创建的TreeNode对象，但**temp仍然指向原来的None**。
3. 最后返回temp，自然会返回None，导致空树插入后没有返回正确的根节点。

修改后的代码中，空树场景下直接给temp赋值TreeNode(val)，此时temp指向新创建的节点，返回temp就能正确返回新的根节点，解决了空树插入的问题。

对于非空树的场景，原代码能正常运行是因为：此时我们是在修改已有节点的left或right引用（比如prev_node.right = TreeNode(val)），这些修改会作用于实际的树对象上，而temp始终指向原根节点，所以返回temp是正确的。

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