Trie树字符串删除方法出现意外错误，请求排查代码问题

先看你代码里的几个关键错误：

1. 调用deleteString时传参错误 #

你调用deleteString(newTrie,"App",0)时，第一个参数传的是Trie类的实例，但deleteString函数的第一个参数期望的是TrieNode类型（因为函数里直接访问root.children）。newTrie是Trie对象，它的root属性才是根节点TrieNode，所以正确调用应该是deleteString(newTrie.root,"App",0)。

2. 遗漏return语句导致逻辑错误 #

在这段代码里：

if currentNode.endOfString==True:
    deleteString(currentNode,word,index+1)
    False

最后一行的False没有加return，这行代码完全无效，函数会继续执行后续逻辑，导致删除逻辑混乱。应该改成return False。

3. 未处理currentNode为None的情况 #

如果要删除的字符串不存在于Trie中，currentNode=root.children.get(ch)会返回None，之后访问currentNode.children会直接抛出AttributeError。需要先判断currentNode是否为None，提前返回。

修正后的完整代码 #

class TrieNode:
    def __init__(self):
        self.children={}
        self.endOfString=False
class Trie:
    def __init__(self):
        self.root=TrieNode()
    
    def insertString(self,word):
        current=self.root  
        for i in word:
            ch=i
            node=current.children.get(ch)
            if node==None:
                node=TrieNode()
                current.children.update({ch:node})
            current=node
        current.endOfString=True
        print("Successfully inserted")

    def searchString(self,word):
        currentNode=self.root
        for i in word:
            node=currentNode.children.get(i)
            if node==None:
                return False
            currentNode=node
        
        return currentNode.endOfString
    
def deleteString(root,word,index):
    if index >= len(word):
        return False
    
    ch=word[index]
    currentNode=root.children.get(ch)
    
    # 处理要删除的字符串不存在的情况
    if not currentNode:
        return False

    canThisNodeBeDeleted = False

    if len(currentNode.children)>1:
         deleteString(currentNode,word,index+1)
         return False
    
    if index==len(word)-1:
        if len(currentNode.children)>=1:
            currentNode.endOfString=False
            return False
        else :
            root.children.pop(ch)
            return True
        
    if currentNode.endOfString==True:
        deleteString(currentNode,word,index+1)
        return False
    
    canThisNodeBeDeleted=deleteString(currentNode,word,index+1)
    if canThisNodeBeDeleted==True:
        root.children.pop(ch)
        return True
    else :
        return False


newTrie=Trie()
newTrie.insertString("App")
newTrie.insertString("Appl")
# 修正传参，传入根节点
deleteString(newTrie.root,"App",0)
print(newTrie.searchString("App")) # 输出False，符合预期
print(newTrie.searchString("Appl")) # 输出True，符合预期

验证结果 #

修正后，删除"App"后，搜索"App"会返回False，而"Appl"仍然可以被搜到，符合Trie树删除的预期逻辑：因为"App"是"Appl"的前缀，删除"App"只需要把对应节点的endOfString设为False，而不是删除节点本身。

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