leetcode 207. Course Schedule , 210. Course Schedule ii
基本上都是可以用backtracking做的,思路也很简单。但是碰到这些graph traversal 的一般来说用Topological Sort比较简单,就是看每个vertex有没有indegree的edge。
time complexity和space complexity 一般都是O(V+E) 点和边
310. Minimum Height Trees
这道题目比较tricky的地方是,如果一个比较直观的solution,用Topological sort做,那么它有一个结论是,通过剪枝最后剩下的那一个或者两个就是最小高度树的树根。
网友评论