Since a tree is an undirected graph in which any two vertices are connected by exactly one path, the number of nodes should be 1 more than the number of edges. So the code should be very simple...
def validTree(self, n, edges): return n == len(edges) + 1
I've just pushed some additional test cases, please try submitting again. And many thanks to @StefanPochmann for contributing one of the test cases! Stefan had contributed a lot to the LeetCode community posting amazing elegant solutions, reviewing almost every problem and test cases. LeetCode could not have achieved such popularity without your important contribution! Thanks Stefan!
An obvious counter example:
4, [[0, 1], [0, 2], [1, 2]]
This graph is not connected and contains cycle. So it is not a tree.
Yes, correct, this solution can only pass at the beginning when test cases are not enough.
@1337c0d3r I think you're exaggerating a bit, but thanks, I'm happy when my stuff helps :-)
@caikehe Just in case you're wondering, I can see/solve problems before they're published, but if I do, I try to not get an "unfair advantage" and wait a bit before I post my solutions.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.