package leetcode;

import java.util.List;

/**
 * https://leetcode.com/problems/throne-inheritance/
 */
public class Problem1600 {
    static class ThroneInheritance {
        public ThroneInheritance(String kingName) {
            // TODO
        }

        public void birth(String parentName, String childName) {
            // TODO
        }

        public void death(String name) {
            // TODO
        }

        public List<String> getInheritanceOrder() {
            // TODO
            return null;
        }
    }

    public static void main(String[] args) {
        Problem1600 prob = new Problem1600();
        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
        System.out.println(t.getInheritanceOrder()); // return ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
        t.death("bob"); // order: king > andy > matthew > bob > alex > asha > catherine
        System.out.println(t.getInheritanceOrder()); // return ["king", "andy", "matthew", "alex", "asha", "catherine"]
    }
}

@@ -29,20 +29,96 @@
 va.util.
-List
+ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
 ;%0A%0A/**%0A 
@@ -250,146 +250,243 @@
    p
-ublic ThroneInheritance(String kingName) %7B%0A            // TODO%0A        %7D%0A%0A        public void birth(String parentName, String childName) %7B
+rivate static class Node %7B%0A            private String name;%0A            private boolean death;%0A            private final List%3CNode%3E children = new ArrayList%3C%3E();%0A%0A            public Node(String name) %7B%0A                this.name = name;
 %0A   
@@ -486,39 +486,33 @@
 me;%0A            
-// TODO
+%7D
 %0A        %7D%0A%0A    
@@ -520,166 +520,226 @@
    p
-ublic void death(String name) %7B%0A            // TODO%0A        %7D%0A%0A        public List%3CString%3E getInheritanceOrder() %7B%0A            // TODO%0A            return null
+rivate final Node root;%0A        private final Map%3CString, Node%3E nodes = new HashMap%3C%3E();%0A%0A        public ThroneInheritance(String kingName) %7B%0A            root = new Node(kingName);%0A            nodes.put(kingName, root)
 ;%0A  
@@ -746,23 +746,21 @@
       %7D%0A
+%0A
     
-%7D%0A%0A
     publ
@@ -766,85 +766,104 @@
 lic 
-static void main(String%5B%5D args) %7B%0A        Problem1600 prob = new Problem1600(
+void birth(String parentName, String childName) %7B%0A            Node parent = nodes.get(parentName
 );%0A 
@@ -873,873 +873,1059 @@
     
+  
-ThroneInheritance t= new ThroneInheritance(%22king%22); // order: king%0A        t.birth(%22king%22, %22andy%22); // order: king %3E andy%0A        t.birth(%22king%22, %22bob%22); // order: king %3E andy %3E bob%0A        t.birth(%22king%22, %22catherine%22); // order: king %3E andy %3E bob %3E catherine%0A        t.birth(%22andy%22, %22matthew%22); // order: king %3E andy %3E matthew %3E bob %3E catherine%0A        t.birth(%22bob%22, %22alex%22); // order: king %3E andy %3E matthew %3E bob %3E alex %3E catherine%0A        t.birth(%22bob%22, %22asha%22); // order: king %3E andy %3E matthew %3E bob %3E alex %3E asha %3E catherine%0A        System.out.println(t.getInheritanceOrder()); // return %5B%22king%22, %22andy%22, %22matthew%22, %22bob%22, %22alex%22, %22asha%22, %22catherine%22%5D%0A        t.death(%22bob%22); // order: king %3E andy %3E matthew %3E bob %3E alex %3E asha %3E catherine%0A        System.out.println(t.getInheritanceOrder()); // return %5B%22king%22, %22andy%22, %22matthew%22, %22alex%22, %22asha%22, %22catherine%22%5D
+  if (parent != null) %7B%0A                Node child = new Node(childName);%0A                parent.children.add(child);%0A                nodes.put(childName, child);%0A            %7D%0A        %7D%0A%0A        public void death(String name) %7B%0A            Node node = nodes.get(name);%0A            if (node != null) %7B%0A                node.death = true;%0A            %7D%0A        %7D%0A%0A        public List%3CString%3E getInheritanceOrder() %7B%0A            List%3CString%3E inheritance = new ArrayList%3C%3E();%0A            if (!root.death) %7B%0A                inheritance.add(root.name);%0A            %7D%0A            getInheritanceOrder(root, inheritance);%0A            return inheritance;%0A        %7D%0A%0A        private static void getInheritanceOrder(Node parent, List%3CString%3E inheritance) %7B%0A            if (parent == null) %7B%0A                return;%0A            %7D%0A            for (Node child : parent.children) %7B%0A                if (!child.death) %7B%0A                    inheritance.add(child.name);%0A                %7D%0A                getInheritanceOrder(child, inheritance);%0A            %7D%0A        %7D
 %0A   

Solve problem 1600