Python基于前序遍历重构BST递归函数去辅助函数后报错排查

问题根因 #

你遇到的报错本质是踩了Python可变默认参数的经典陷阱：

• Python中函数的默认参数值是在函数定义阶段初始化的，而非每次调用函数时重新生成
• 你改写后的代码里把root_index=[0]设为默认参数，这个列表只会在函数第一次定义时创建一次，后续所有不带root_index参数的调用都会复用同一个列表对象
• 第一次运行测试用例时root_index[0]会正常递增到输入数组的长度，第二个测试用例调用时，root_index[0]已经不是初始值0，而是上一次调用结束后的数值，判断失效后直接访问索引就会抛出越界错误。

修复方案 #

只要把root_index的默认值改成不可变的None，在函数内部每次顶层调用时初始化即可，修改后的代码如下：

class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def reconstructBst(preOrderTraversalValues, low=float("-inf"), high=float("inf"), root_index=None):
    # 每次顶层调用重新初始化root_index，避免复用旧对象
    if root_index is None:
        root_index = [0]
    if root_index[0] == len(preOrderTraversalValues):
        return None
    
    root_value = preOrderTraversalValues[root_index[0]]
    if root_value < low or root_value >= high:
        return None
    
    root_index[0] += 1
    left_subtree = reconstructBst(preOrderTraversalValues, low, root_value, root_index)
    right_subtree = reconstructBst(preOrderTraversalValues, root_value, high, root_index)
    return BST(root_value, left_subtree, right_subtree)

修改后每次顶层调用函数都会生成新的root_index列表，不同测试用例之间不会互相干扰，即可正常运行。

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