Leetcode 1600. Throne Inheritance (python)

题目

题目太长了，直接放链接吧 https://leetcode.com/problems/throne-inheritance/

解法：

这道题目实际上是个树的preorder visit，然后储存的时候用字典的方式来保存父节点和子节点之间的关系
一开始写的时候TLE了，先看看错误的写法：

class ThroneInheritance:def __init__(self, kingName: str):self.d = collections.defaultdict(list)self.death_list = []self.kingName = kingNameself.inherit_list = [kingName]def birth(self, parentName: str, childName: str) -> None:self.d[parentName].append(childName)def death(self, name: str) -> None:self.death_list.append(name)def getInheritanceOrder(self) -> List[str]:def dfs(curName):if curName not in self.death_list:ans.append(curName)if curName not in self.d:returnfor child in self.d[curName]:dfs(child)ans = []dfs(self.kingName)return ans

这里的TLE主要是因为一个元素判断是不是在这个列表中是O(n)的，所以才会超时，简单的改成字典来储存

class ThroneInheritance:def __init__(self, kingName: str):self.d = collections.defaultdict(list)self.death_dict = {
    }self.kingName = kingNamedef birth(self, parentName: str, childName: str) -> None:self.d[parentName].append(childName)def death(self, name: str) -> None:self.death_dict[name] = Truedef getInheritanceOrder(self) -> List[str]:def dfs(curName):if curName not in self.death_dict:ans.append(curName)if curName not in self.d:returnfor child in self.d[curName]:dfs(child)ans = []dfs(self.kingName)return ans

follow up

了解一下hash机制