刷题(15)Topological Sort

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做,那么它有一个结论是,通过剪枝最后剩下的那一个或者两个就是最小高度树的树根。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容