My dfs solution


  • 0
    W
    public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges == null || edges.length == 0) {
            return (n == 1);
        }
        HashMap<Integer, ArrayList<Integer>> neighbor = new HashMap<Integer,  ArrayList<Integer>>();
        for (int i = 0; i < n; i++) {
            neighbor.put(i, new ArrayList<Integer>());
        }
        int[] isVisited = new int[n];
        for (int[] edge : edges){
            neighbor.get(edge[0]).add(edge[1]); 
            neighbor.get(edge[1]).add(edge[0]); 
            
        }
        boolean a = dfs(edges[0][0], isVisited, neighbor);
        for (int i = 0; i < isVisited.length; i++) {
            if (isVisited[i] == 0)
            return false;
        }
        return a;
    }
    
    private boolean dfs (int x, int[] isVisited, 
                         HashMap<Integer, ArrayList<Integer>> neighbor)
    {
        boolean ans = true;
        isVisited[x] = 1;
        for (int i : neighbor.get(x)) {
            if (isVisited[i] == 2) {  //这里要先判断,再进入dfs,不然必然为2;
                return false;
            }
            if (isVisited[i] == 0){
                ans = dfs(i, isVisited, neighbor) && ans;
            } 
        }
        isVisited[x] = 2;
        return ans;
    }
    

    }


Log in to reply
 

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