Python Stack based 60 ms


  • 0
    B
    class Solution(object):
        def validTree(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: bool
            """
            self.adj_list = {x:[] for x in range (n)}
            self.isVisited = [0]*n
            retVal = 0
            self.stack = []
            for x, y in edges:
                self.adj_list[x].append(y)
                self.adj_list[y].append(x)
            for node in self.adj_list:
                if self.isVisited[node]:
                    continue
                self.stack.append((node,None))
                while(self.stack):
                    currnode = self.stack.pop()
                    if self.isVisited[currnode[0]] != 0:
                        return False
                    self.isVisited[currnode[0]] = 1
                    for x in self.adj_list[currnode[0]]:
                        if x == currnode[1]:
                            continue
                        if self.isVisited[x] != 0:
                            return False
                        self.stack.append((x,currnode[0]))
                retVal += 1
    
            if retVal > 1:
                return False
            else:
                return True

Log in to reply
 

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