如何在Python中不使用return语句递归构建二叉搜索树？

原代码失效原因 #

你编写的无return的insert_1无法完成树构建的核心原因是Python的参数传递规则：Python中所有参数均为传对象引用，当你在函数内部直接对参数变量root执行赋值操作root = treeNode(key)时，仅会修改当前函数作用域内的局部变量指向，不会修改外层父节点的leftChild/rightChild属性，新创建的节点没有绑定到树结构上，因此构建失败。

无return的实现方案 #

无需return即可实现递归构建二叉搜索树，核心思路是提前判断子节点是否为空，直接对父节点的子节点属性赋值，避免对参数变量本身做赋值操作，实现代码如下：

import numpy as np

class treeNode:
    def __init__(self,key):
        self.leftChild = None
        self.rightChild = None
        self.value = key

def insert_no_return(root, key):
    if root.value == key:
        return
    # 处理右子树插入
    elif root.value < key:
        if root.rightChild is None:
            # 直接修改父节点的右子节点属性，生效到原实例
            root.rightChild = treeNode(key)
        else:
            insert_no_return(root.rightChild, key)
    # 处理左子树插入
    else:
        if root.leftChild is None:
            # 直接修改父节点的左子节点属性，生效到原实例
            root.leftChild = treeNode(key)
        else:
            insert_no_return(root.leftChild, key)

def construct_tree(a):
    if not a:
        return None
    root = treeNode(a[0])
    # 跳过第一个元素避免重复插入根节点
    for k in a[1:]:
        insert_no_return(root, k)
    return root

if __name__ == '__main__':
    np.random.seed(1)
    a = np.random.rand(12)
    tree_1 = construct_tree(a)

验证说明 #

上述代码完全没有使用return传递新建节点，所有节点绑定都通过修改已有节点的属性完成，属性修改会直接作用到原实例对象上，可正常构建完整的二叉搜索树。

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