[Java] Detailed Explanation - Build Tree + DFS
[Updated] Still need bi-direction graph and use visited set. Example test case for that: (Thanks @hiepit and @notebook, my bad)\n4\n[[0,2],[0,3],[1,2]]\n[false,
**[Updated]** Still need bi-direction graph and use visited set. Example test case for that: (Thanks @hiepit and @notebook, my bad)\n*4\n[[0,2],[0,3],[1,2]]\n[false,true,false,false]\nExpected Answer: 4*\n\nKey Notes: \n* You need to consume 2 seconds to simply collect an apple node (come and go)\n* Consider a node:\n\t* If none of descendant (including itself) has an apple, we don\'t need to waste time on this node\n\t* If any of descendant has an apple (no matter if it-self has an apple or not), we need to consume 2 seconds on this node anyway\n* Collect node 0 does not need to consume any time\n\nThen, we can have a helper dfs function meaning: time needs to waste on this node to collect all apples. (0 or > 0).\n\n```java\npublic int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        \n\tMap<Integer, List<Integer>> map = new HashMap<>();\n\tbuildTree(edges, map);\n\tSet<Integer> visited = new HashSet<>();\n\treturn helper(0, map, hasApple, visited);\n}\n\nprivate int helper(int node, Map<Integer, List<Integer>> map, List<Boolean> hasApple, Set<Integer> visited) {\n\n\tvisited.add(node);\n\n\tint res = 0;\n\n\tfor (int child : map.getOrDefault(node, new LinkedList<>())) {\n\t\tif (visited.contains(child)) continue;\n\t\tres += helper(child, map, hasApple, visited);\n\t}\n\n\tif ((res > 0 || hasApple.get(node)) && node != 0) res += 2;\n\n\treturn res;\n}\n\nprivate void buildTree(int[][] edges, Map<Integer, List<Integer>> map) {\n\n\tfor (int[] edge : edges) {\n\t\tint a = edge[0], b = edge[1];\n\t\tmap.putIfAbsent(a, new LinkedList<>());\n\t\tmap.putIfAbsent(b, new LinkedList<>());\n\t\tmap.get(a).add(b);\n\t\tmap.get(b).add(a);\n\t}\n\n}\n```
[]