AC Java DFS Solution


  • 0
    Q
    public class Solution {
        public boolean validTree(int n, int[][] edges) {
            List<List<Integer>> graph = new ArrayList<>();
            for(int i = 0; i < n; i++) {
                graph.add(new ArrayList<>());
            }
            for(int[] edge : edges) {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
            boolean[] visited = new boolean[n];
            if(!dfs(graph, visited, 0, -1)) return false;
            for(boolean visit : visited) {
                if(!visit) return false;
            }
            return true;
        }
    
        private boolean dfs(List<List<Integer>> graph, boolean[] visited, int kid, int parent) {
            if(visited[kid]) return false;
            visited[kid] = true;
            for(int neighbor : graph.get(kid)) {
                if(neighbor != parent && !dfs(graph, visited, neighbor, kid)) return false;
            }
            return true;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.