_1600.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.ArrayList;
importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

publicclass_1600 {
publicstaticclassSolution1 {
/*
 * My completely original solution:
 * 1. use a tree structure to represent the king family;
 * 2. then use preorder traversal to find the inheritance order;
 * 3. use a map to quickly find the corresponding node in the tree based on the name since all names are distinct
 */
publicstaticclassPerson {
List<Person> children;
Stringname;
booleanisAlive;

publicPerson(StringkingName) {
this.name = kingName;
this.children = newArrayList<>();
this.isAlive = true;
 }
 }

publicstaticclassThroneInheritance {
Personking;
Map<String, Person> map;
StringkingName;

publicThroneInheritance(StringkingName) {
king = newPerson(kingName);
map = newHashMap<>();
this.kingName = kingName;
map.put(kingName, king);
 }

publicvoidbirth(StringparentName, StringchildName) {
PersonparentNode = map.getOrDefault(parentName, newPerson(parentName));
Personchild = newPerson(childName);
parentNode.children.add(child);
map.put(parentName, parentNode);
map.put(childName, child);
 }

publicvoiddeath(Stringname) {
PersondeadPerson = map.get(name);
deadPerson.isAlive = false;
map.put(name, deadPerson);
 }

publicList<String> getInheritanceOrder() {
returnpreorder(map.get(this.kingName), newArrayList<>());
 }

privateList<String> preorder(Personperson, List<String> list) {
if (person == null) {
returnlist;
 }
if (person.isAlive) {
list.add(person.name);
 }
for (Personchild : person.children) {
preorder(child, list);
 }
returnlist;
 }
 }
 }
}