[leetcode] 1600. Throne Inheritance

[leetcode] 1600. Throne Inheritance

Description

A kingdom consists of a king, his children, his grandchildren, and so on. Every once in a while, someone in the family dies or a child is born.

The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let’s define the recursive function Successor(x, curOrder), which given a person x and the inheritance order so far, returns who should be the next person after x in the order of inheritance.

Successor(x, curOrder): if x has no children or all of x's children are in curOrder: if x is the king return null else return Successor(x's parent, curOrder) else return x's oldest child who's not in curOrder

For example, assume we have a kingdom that consists of the king, his children Alice and Bob (Alice is older than Bob), and finally Alice’s son Jack.

In the beginning, curOrder will be [“king”].Calling Successor(king, curOrder) will return Alice, so we append to curOrder to get [“king”, “Alice”].Calling Successor(Alice, curOrder) will return Jack, so we append to curOrder to get [“king”, “Alice”, “Jack”].Calling Successor(Jack, curOrder) will return Bob, so we append to curOrder to get [“king”, “Alice”, “Jack”, “Bob”].Calling Successor(Bob, curOrder) will return null. Thus the order of inheritance will be [“king”, “Alice”, “Jack”, “Bob”].

Using the above function, we can always obtain a unique order of inheritance.

Implement the ThroneInheritance class:

ThroneInheritance(string kingName) Initializes an object of the ThroneInheritance class. The name of the king is given as part of the constructor.void birth(string parentName, string childName) Indicates that parentName gave birth to childName.void death(string name) Indicates the death of name. The death of the person doesn’t affect the Successor function nor the current inheritance order. You can treat it as just marking the person as dead.string[] getInheritanceOrder() Returns a list representing the current order of inheritance excluding dead people.Example 1:

Input["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"][["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]Output[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]ExplanationThroneInheritance t= new ThroneInheritance("king"); // order: kingt.birth("king", "andy"); // order: king > andyt.birth("king", "bob"); // order: king > andy > bobt.birth("king", "catherine"); // order: king > andy > bob > catherinet.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherinet.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherinet.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherinet.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherinet.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]

Constraints:

1 <= kingName.length, parentName.length, childName.length, name.length <= 15kingName, parentName, childName, and name consist of lowercase English letters only.All arguments childName and kingName are distinct.All name arguments of death will be passed to either the constructor or as childName to birth first.For each call to birth(parentName, childName), it is guaranteed that parentName is alive.At most 105 calls will be made to birth and death.At most 10 calls will be made to getInheritanceOrder.

分析

题目的意思是：实现一个王权继承算法，这道题我看了一下提示需要构造树，并且加入death的属性，然后在遍历的时候跳过dead的结点就行了。其实可以用python里面的字典来实现这一过程，其中字典d存储的是当前节点的孩子节点，dead存储的是死亡的节点，getInheritanceOrder在遍历的时候也可以递归的遍历，即从kingName开始深度优先遍历就行了。

代码

class ThroneInheritance: def __init__(self, kingName: str): self.kingName=kingName self.d=collections.defaultdict(list) self.dead={} def birth(self, parentName: str, childName: str) -> None: self.d[parentName].append(childName) def death(self, name: str) -> None: self.dead[name]=False def solve(self,name): if(name not in self.dead): ans=[name] else: ans=[] for item in self.d[name]: ans+=self.solve(item) return ans def getInheritanceOrder(self) -> List[str]: return self.solve(self.kingName) # Your ThroneInheritance object will be instantiated and called as such:# obj = ThroneInheritance(kingName)# obj.birth(parentName,childName)# obj.death(name)# param_3 = obj.getInheritanceOrder()

参考文献

​​[LeetCode] [Python] Using Node class​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。