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.<\/p>\n\n\n\n
The kingdom has a well-defined order of inheritance that consists of the king as the first member. Let’s define the recursive function 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.<\/p>\n\n\n\n Using the above function, we can always obtain a unique order of inheritance.<\/p>\n\n\n\n Implement the Example 1:<\/strong><\/p>\n\n\n\n Constraints:<\/strong><\/p>\n\n\n\n Record : Time complexity: getInheritanceOrder O(n), other O(1) 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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[153],"tags":[33,82,177,17],"class_list":["post-7425","post","type-post","status-publish","format-standard","hentry","category-recursion","tag-dfs","tag-hashtable","tag-medium","tag-recursion","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7425","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7425"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7425\/revisions"}],"predecessor-version":[{"id":7428,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7425\/revisions\/7428"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7425"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7425"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7425"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Successor(x, curOrder)<\/code>, which given a person x<\/code> and the inheritance order so far, returns who should be the next person after x<\/code> in the order of inheritance.<\/p>\n\n\n\nSuccessor(x, curOrder):\n if x has no children or all of x's children are in curOrder:\n if x is the king return null\n else return Successor(x's parent, curOrder)\n else return x's oldest child who's not in curOrder\n<\/pre>\n\n\n\n
curOrder<\/code> will be [\"king\"]<\/code>.<\/li>Successor(king, curOrder)<\/code> will return Alice, so we append to curOrder<\/code> to get [\"king\", \"Alice\"]<\/code>.<\/li>Successor(Alice, curOrder)<\/code> will return Jack, so we append to curOrder<\/code> to get [\"king\", \"Alice\", \"Jack\"]<\/code>.<\/li>Successor(Jack, curOrder)<\/code> will return Bob, so we append to curOrder<\/code> to get [\"king\", \"Alice\", \"Jack\", \"Bob\"]<\/code>.<\/li>Successor(Bob, curOrder)<\/code> will return null<\/code>. Thus the order of inheritance will be [\"king\", \"Alice\", \"Jack\", \"Bob\"]<\/code>.<\/li><\/ol>\n\n\n\nThroneInheritance<\/code> class:<\/p>\n\n\n\nThroneInheritance(string kingName)<\/code> Initializes an object of the ThroneInheritance<\/code> class. The name of the king is given as part of the constructor.<\/li>void birth(string parentName, string childName)<\/code> Indicates that parentName<\/code> gave birth to childName<\/code>.<\/li>void death(string name)<\/code> Indicates the death of name<\/code>. The death of the person doesn’t affect the Successor<\/code> function nor the current inheritance order. You can treat it as just marking the person as dead.<\/li>string[] getInheritanceOrder()<\/code> Returns a list representing the current order of inheritance excluding<\/strong> dead people.<\/li><\/ul>\n\n\n\nInput<\/strong>\n[\"ThroneInheritance\", \"birth\", \"birth\", \"birth\", \"birth\", \"birth\", \"birth\", \"getInheritanceOrder\", \"death\", \"getInheritanceOrder\"]\n[[\"king\"], [\"king\", \"andy\"], [\"king\", \"bob\"], [\"king\", \"catherine\"], [\"andy\", \"matthew\"], [\"bob\", \"alex\"], [\"bob\", \"asha\"], [null], [\"bob\"], [null]]\nOutput<\/strong>\n[null, null, null, null, null, null, null, [\"king\", \"andy\", \"matthew\", \"bob\", \"alex\", \"asha\", \"catherine\"], null, [\"king\", \"andy\", \"matthew\", \"alex\", \"asha\", \"catherine\"]]\nExplanation<\/strong>\nThroneInheritance t= new ThroneInheritance(\"king\"); \/\/ order: king<\/strong>\nt.birth(\"king\", \"andy\"); \/\/ order: king > andy<\/strong>\nt.birth(\"king\", \"bob\"); \/\/ order: king > andy > bob<\/strong>\nt.birth(\"king\", \"catherine\"); \/\/ order: king > andy > bob > catherine<\/strong>\nt.birth(\"andy\", \"matthew\"); \/\/ order: king > andy > matthew<\/strong> > bob > catherine\nt.birth(\"bob\", \"alex\"); \/\/ order: king > andy > matthew > bob > alex<\/strong> > catherine\nt.birth(\"bob\", \"asha\"); \/\/ order: king > andy > matthew > bob > alex > asha<\/strong> > catherine\nt.getInheritanceOrder(); \/\/ return [\"king\", \"andy\", \"matthew\", \"bob\", \"alex\", \"asha\", \"catherine\"]\nt.death(\"bob\"); \/\/ order: king > andy > matthew >
bob<\/s><\/strong> > alex > asha > catherine\nt.getInheritanceOrder(); \/\/ return [\"king\", \"andy\", \"matthew\", \"alex\", \"asha\", \"catherine\"]\n<\/p>\n<\/pre>\n\n\n\n1 <= kingName.length, parentName.length, childName.length, name.length <= 15<\/code><\/li>kingName<\/code>, parentName<\/code>, childName<\/code>, and name<\/code> consist of lowercase English letters only.<\/li>childName<\/code> and kingName<\/code> are distinct<\/strong>.<\/li>name<\/code> arguments of death<\/code> will be passed to either the constructor or as childName<\/code> to birth<\/code> first.<\/li>birth(parentName, childName)<\/code>, it is guaranteed that parentName<\/code> is alive.<\/li>105<\/sup><\/code> calls will be made to birth<\/code> and death<\/code>.<\/li>10<\/code> calls will be made to getInheritanceOrder<\/code>.<\/li><\/ul>\n\n\n\nSolution: HashTable + DFS<\/strong><\/h2>\n\n\n\n
1. mapping from parent to children (ordered)
2. who has dead<\/p>\n\n\n\n
Space complexity: O(n)<\/p>\n\n\n\nC++<\/h2>\n
\n\/\/ Author: Huahua\nclass ThroneInheritance {\npublic:\n ThroneInheritance(string kingName): king_(kingName) {\n m_[kingName] = {};\n }\n\n void birth(string parentName, string childName) {\n m_[parentName].push_back(childName);\n }\n\n void death(string name) {\n dead_.insert(name);\n }\n\n vectorPython3<\/h2>\n
\n# Author: Huahua\nclass ThroneInheritance:\n def __init__(self, kingName: str):\n self.kingName = kingName\n self.family = defaultdict(list) \n self.dead = set()\n\n def birth(self, parentName: str, childName: str) -> None:\n self.family[parentName].append(childName)\n\n def death(self, name: str) -> None:\n self.dead.add(name)\n\n def getInheritanceOrder(self) -> List[str]:\n order = []\n def dfs(name: str):\n if name not in self.dead: order.append(name)\n for child in self.family[name]: dfs(child)\n dfs(self.kingName)\n return order\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"