分治/递归 综合解法:
- 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
链表的分治/递归:
- Remove Duplicates from Sorted List
- Reverse Linked List