java dfs sorting
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n     public  long[] placedCoins(int[][] edges, int[] cost) {\n\n        // 1. root\uC5D0\uC11C leaf node\uAE4C\uC9C0 \uD0C0\uACE0 \uB4E4\uC5B4\uAC04\uB2E4\uC74C \n        //    minusList, plusList \uC5D0 \uAC01\uAC01 3\uAC1C\uC529 \uC22B\uC790\uB97C \uC720\uC9C0\uD558\uBA74\uC11C parent node\uB85C \uC62C\uB824\uC900\uB2E4. \n        //    minusList : \uC74C\uC218(0\uD3EC\uD568) \uC911 \uAC00\uC7A5 \uC791\uC740 \uAC83 \uC138\uAC1C\n        //    plusList :  \uC591\uC218 \uC911 \uAC00\uC7A5 \uD070 \uAC83 \uC138\uAC1C \n        \n        // 2. 1) leaf node\uC5D0\uC11C \uBC1B\uC740 \uAC83\uACFC \uD604\uC7AC node\uC5D0\uC11C \uC720\uC9C0\uD558\uACE0 \uC788\uB294 list\uB97C \uD1B5\uD569 \n        //    2) \uC815\uB82C (\uCD5C\uB300 6\uAC1C\uB77C \uC131\uB2A5\uC5D0 \uC601\uD5A5\uC740 \uC5C6\uB2E4. )\n        //    3) minusList \uB4A4\uC5D0\uC11C\uBD80\uD130 3\uAC1C \uCD08\uACFC\uB41C \uAC83\uB4E4 \uC81C\uAC70\n        //    4) plusList \uC55E\uC5D0\uC11C\uBD80\uD130 3\uAC1C \uCD08\uACFC\uB41C \uAC1C\uC218\uB97C \uC81C\uAC70 \n\n        // 3. minusList.size() + plusList.size() \uAC00 3\uBCF4\uB2E4 \uC791\uC73C\uBA74 result[node] \uC5D0 1\uC744 \uB123\uACE0 \n        //    minusList.size() + plusList.size() \uAC00 3\uBCF4\uB2E4 \uD06C\uAC70\uB098 \uAC19\uC73C\uBA74 \n        //    1) minusList \uC758 \uAC00\uC7A5 \uC791\uC740 \uB450\uAC1C * plusList\uC758 \uAC00\uC7A5 \uD070\uAC83 \uD55C\uAC1C \n        //    2) plusList \uC5D0\uC11C \uD070 \uAC83 \uC138\uAC1C \n        //    3) 1),2) \uC911 \uD070 \uAC83\uC744 result[node] \uC5D0 \uB123\uC5B4\uC900\uB2E4. \n\n        \n        int n = edges.length;\n        List<List<Integer>> graph = new ArrayList<List<Integer>>();\n        for(int i = 0; i <= n; i++) graph.add(new ArrayList<Integer>());\n\n        for(int i = 0; i < edges.length; i++) {\n            int a = edges[i][0];\n            int b = edges[i][1];\n            \n            graph.get(a).add(b);\n            graph.get(b).add(a);\n        }\n\n        // for(int i = 0; i < graph.size(); i++) {\n        //     System.out.print(i + "] ");\n        //     for(int j = 0; j < graph.get(i).size(); j++) {\n        //         System.out.print("[" + graph.get(i).get(j) + "]");\n        //     }\n        //     System.out.println();\n        // }\n\n        long result[] = new long[n+1];\n        dfs(0, -1, graph, cost, result);\n\n        // for(int i = 0; i <result.length; i++) System.out.print(result[i] + " "); System.out.println();\n\n        return result;\n    }\n\n    private  List<List<Integer>> dfs(int node, int parent, List<List<Integer>> graph, int[] cost, long result[]) {\n\nList<List<Integer>> list = new ArrayList<List<Integer>>();\n        \n        List<Integer> minusList = new ArrayList<Integer>();\n        List<Integer> plusList = new ArrayList<Integer>();\n\n\n        if ( cost[node] <= 0 ) minusList.add(cost[node]);\n        else {\n            plusList.add(cost[node]);\n        }\n\n        int nextNode = 0;\n        List<List<Integer>> returnList;\n        for(int i = 0; i < graph.get(node).size(); i++) {\n            nextNode = graph.get(node).get(i);\n            if ( nextNode == parent) continue;\n\n            returnList = dfs(nextNode, node, graph, cost, result);\n\n            for(int j = 0; j < returnList.get(0).size(); j++) {\n                minusList.add(returnList.get(0).get(j));\n            }\n\n            for(int j = 0; j < returnList.get(1).size(); j++) {\n                plusList.add(returnList.get(1).get(j));\n            }\n\n            Collections.sort(minusList);\n            Collections.sort(plusList);\n\n            while(minusList.size() > 3 )  {\n                minusList.remove(minusList.size()-1);\n            }\n            \n            while(plusList.size() > 3 )  {\n                plusList.remove(0);\n            }\n        }\n\n        if ( minusList.size() + plusList.size() < 3 ) {\n            result[node] = 1;\n        } else {\n            long max = 0;\n\n            if ( minusList.size() >= 2 && plusList.size() > 0 ) {\n                max = Math.max(max, (long)minusList.get(0) * minusList.get(1) * plusList.get(plusList.size()-1));\n            }\n\n            if ( plusList.size() == 3 ) {\n                max = Math.max(max, (long)plusList.get(0) * plusList.get(1) * plusList.get(2));\n            }\n\n            result[node] = max;\n        }\n \n            \n        \n        \n        // System.out.println(node + " " + minusList + " " + plusList);\n        \n        list.add(minusList);\n        list.add(plusList);\n\n        return list;\n    }\n}\n```
['Depth-First Search', 'Sorting', 'Java']