Beats 100% users with java
\n\n# Approach\n Describe your approach to solving the problem. \n1. The getAncestors method takes two parameters, an integer n representing the number of nodes
![image.png](https://assets.leetcode.com/users/images/92a14934-9e74-4a1e-ab9b-0f8098e91b08_1719679265.4501069.png)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. The getAncestors method takes two parameters, an integer n representing the number of nodes and a 2D array edges representing the edges between nodes.\n2. It initializes an empty list res to store the ancestors.\n3. It creates an array of ArrayLists named graph to represent the tree structure.\n4. It initializes each element of the graph array as an empty ArrayList.\n5. It populates the graph array using the edges provided in the input.\n6. It then iterates through each node and calls the dfs method to find the ancestors of that node.\n7. The dfs method performs a depth-first search starting from the current node curr, marking it as visited and exploring its children recursively.\n8. For each unvisited child dest of the current node, it adds the parent of the current node to the dest node\'s list of ancestors in the result list res.\n9. The dfs method continues exploring the descendants of the current node recursively.\n10. Finally, the getAncestors method returns the list res containing the ancestors of each node in the tree.\n\n# Complexity\n- Time complexity:the overall time complexity of the getAncestors method is O(V + E + N).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public List<List<Integer>> getAncestors(int n, int[][] edges) {\n        List<List<Integer>> res=new ArrayList<>();\n        for(int i=0; i<n; i++){\n            res.add(new ArrayList<>());\n        } \n\n        ArrayList<Integer>[] graph=new ArrayList[n];\n        for(int i=0; i<n; i++){\n            graph[i]=new ArrayList<>();\n        }   \n        for(int[] edge: edges){\n            graph[edge[0]].add(edge[1]);\n        }\n        for(int i=0; i<n; i++){\n            dfs(graph,i,i,res,new boolean[n]);\n        }\n        return res;\n    }\n    public void dfs( ArrayList<Integer>[] graph, int parent, int curr, List<List<Integer>> res,boolean[] visit){\n        visit[curr]=true;\n        for(int i=0; i< graph[curr].size(); i++){\n            int dest=graph[curr].get(i);\n            if(!visit[dest]){\n                res.get(dest).add(parent);\n                dfs(graph,parent,dest,res,visit);\n            }\n        }\n    }\n}\n```
['Java']