LeetCode 208前缀树实现：测试用例间内存未清空引发错误

问题描述 #

实现前缀树时，提交测试遇到异常：

• 测试输入：

  ["Trie","startsWith"]
  [[],["a"]]
  

• 预期输出：[null,false]，但代码实际返回[null,true]

调试发现，当前测试用例未执行任何insert操作，但Trie实例中却存在来自之前测试用例的"app"和"apple"节点。虽然平台存在相关遗留问题，但其他用户的AC代码无此问题，说明自身代码存在触发该问题的缺陷。另外，使用调试模式运行相同代码和用例时结果正确。

问题代码 #

from collections import deque

class Trie:
    def __init__(self, children = {}, value = '', is_terminal = False):
        self.children = children
        self.value = value
        self.is_terminal = is_terminal

    def __str__(self):
        s = ''
        s += self.value
        queue = deque([])
        for child in self.children.values():
            queue.append(child)
        while queue:
            node = queue.popleft()
            s += node.value
            if node.is_terminal:
                s += 'T'
            for child in node.children.values():
                queue.append(child)
        return s

    def __repr__(self):
        return self.__str__()

    def get_child(self, val) -> "Trie":
        return self.children[val]

    def has_child(self, val) -> bool:
        return val in self.children

    def set_terminal(self) -> None:
        self.is_terminal = True
        
    def insert(self, word: str) -> None:
        node = self
        for char in word:
            if not node.has_child(char):
                new = Trie({}, char, False)
                node.children[char] = new
            node = node.get_child(char)

        node.set_terminal()

    def search(self, word: str) -> bool:
        node = self
        for char in word:
            if not node.has_child(char):
                return False
            node = node.get_child(char)
        return node.is_terminal

    def startsWith(self, prefix: str) -> bool:
        print(self) # this returns appTleT
        node = self
        for char in prefix:
            if not node.has_child(char):
                return False
            node = node.get_child(char)
        return True

问题原因 #

Python中可变默认参数会被所有实例共享：__init__方法里的children = {}是可变默认参数，第一次创建Trie实例时生成的空字典，会被后续所有新实例复用，导致不同测试用例的Trie实例共享同一套节点数据，出现状态污染。

修复方案 #

修改__init__方法的默认参数，避免使用可变对象作为默认值：

class Trie:
    def __init__(self, children=None, value='', is_terminal=False):
        self.children = children if children is not None else {}
        self.value = value
        self.is_terminal = is_terminal

这样每次创建Trie实例时，都会初始化一个全新的空字典作为children，不会再出现跨测试用例的状态共享问题。

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