Leetcode 1600. Throne Inheritance

题目解法：follow up

题目

题目太长了，直接放链接吧 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 = kingName self.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: return for 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 = kingName def birth(self, parentName: str, childName: str) -> None: self.d[parentName].append(childName) def death(self, name: str) -> None: self.death_dict[name] = True def getInheritanceOrder(self) -> List[str]: def dfs(curName): if curName not in self.death_dict: ans.append(curName) if curName not in self.d: return for child in self.d[curName]: dfs(child) ans = [] dfs(self.kingName) return ans

follow up

了解一下hash机制