递归/分治 总结

分治/递归 综合解法:

  1. think last but write first: 考虑递归终止条件
    1.pre-order先序部分:处理当前
    2.递归到子问题-分治Divide
    3.post-order后序部分:处理当前 (dfs到底后执行)

分治 post-order 和 pre-order 不是非此即彼的问题,看操作的需要,是两个part。
(1) 一般当前level的操作话:既可以在pre部分处理;也可以放在post部分处理,dfs到底后再做。一般放在pre做比较clear~
(2) 分治后的"conquer收集部分并回传结果":如果需要 这个是必须在post做的。

主要是分好 子问题,然后确定当前层操作 以及 子问题和本层操作之间需要的传递的关系,当前操作可以在pre或post

树的分治/递归:
pre-order recursion部分:http://www.jianshu.com/p/f73dc8597db4
post-order recursion 部分:http://www.jianshu.com/p/e1bbefc41237

链表的分治/递归:

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

推荐阅读更多精彩内容