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 tocurOrder
to get["king", "Alice"]
. - Calling
Successor(Alice, curOrder)
will return Jack, so we append tocurOrder
to get["king", "Alice", "Jack"]
. - Calling
Successor(Jack, curOrder)
will return Bob, so we append tocurOrder
to get["king", "Alice", "Jack", "Bob"]
. - Calling
Successor(Bob, curOrder)
will returnnull
. 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 theThroneInheritance
class. The name of the king is given as part of the constructor.void birth(string parentName, string childName)
Indicates thatparentName
gave birth tochildName
.void death(string name)
Indicates the death ofname
. The death of the person doesn't affect theSuccessor
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"]] 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"]
Constraints:
1 <= kingName.length, parentName.length, childName.length, name.length <= 15
kingName
,parentName
,childName
, andname
consist of lowercase English letters only.- All arguments
childName
andkingName
are distinct. - All
name
arguments ofdeath
will be passed to either the constructor or aschildName
tobirth
first. - For each call to
birth(parentName, childName)
, it is guaranteed thatparentName
is alive. - At most
105
calls will be made tobirth
anddeath
. - At most
10
calls will be made togetInheritanceOrder
.
Solutions
Solution 1: Preorder Traversal of a Multi-branch Tree
According to the problem description, we can find that the order of throne inheritance is actually a preorder traversal of a multi-branch tree. We can use a hash table $g$ to store the children of each person, and a set $dead$ to store the people who have died.
- When calling
birth(parentName, childName)
, we addchildName
to the child list ofparentName
. - When calling
death(name)
, we addname
to thedead
set. - When calling
getInheritanceOrder()
, we start a depth-first search from the king. If the current nodex
is not dead, we addx
to the answer list, and then recursively traverse all children ofx
.
In terms of time complexity, both birth
and death
have a time complexity of $O(1)$, and getInheritanceOrder
has a time complexity of $O(n)$. The space complexity is $O(n)$, where $n$ is the number of nodes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
|