#1600
Throne Inheritance
specialist · 670 · lc medium +30 · 66.9% accepted · 319 likes · top 73%
Description
A royal family tree determines succession order via pre-order depth-first traversal. Implement the ThroneInheritance class:
- ThroneInheritance(string kingName) initializes the class with the king's name.
- void birth(string parentName, string childName) records that parentName had a child named childName.
- void death(string name) marks name as dead. Dead members are excluded from the succession order but their descendants remain.
- string[] getInheritanceOrder() returns the current succession list, excluding dead members.
Example 1:
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
Example 2:
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"]]
Example 3:
Explanation
ThroneInheritance t= new ThroneInheritance("king"); // order: king
t.birth("king", "andy"); // order: king > andy
t.birth("king", "bob"); // order: king > andy > bob
t.birth("king", "catherine"); // order: king > andy > bob > catherine
t.birth("andy", "matthew"); // order: king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // order: king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20