Java, simple DFS solution

  • 9
    public boolean validTree(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < adj.length; i++) 
            adj[i] = new ArrayList<Integer>();
        for (int[] edge : edges) {
        if (!dfs(0, -1, visited, adj)) return false;
        for (boolean b : visited)
            if (!b) return false;
        return true;
    // p is the pointer to 'parent' node, we ignore it to avoid infinite loop
    private boolean dfs(int v, int p, boolean[] visited, List<Integer>[] adj) {
        visited[v] = true;
        for (int i : adj[v]) {
            if (i == p) continue;
            if (visited[i] || !dfs(i, v, visited, adj)) return false;
        return true;

Log in to reply

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