分治/遞歸 綜合解法:
- think last but write first: 考慮遞歸終止條件
1.pre-order先序部分:處理當(dāng)前
2.遞歸到子問題-分治Divide
3.post-order后序部分:處理當(dāng)前 (dfs到底后執(zhí)行)
分治 post-order 和 pre-order 不是非此即彼的問題,看操作的需要染突,是兩個(gè)part妈候。
(1) 一般當(dāng)前l(fā)evel的操作話:既可以在pre部分處理源武;也可以放在post部分處理彤钟,dfs到底后再做胳搞。一般放在pre做比較clear~
(2) 分治后的"conquer收集部分并回傳結(jié)果":如果需要 這個(gè)是必須在post做的会前。
主要是分好 子問題,然后確定當(dāng)前層操作 以及 子問題和本層操作之間需要的傳遞的關(guān)系蛔溃,當(dāng)前操作可以在pre或post
樹的分治/遞歸:
pre-order recursion部分:http://www.reibang.com/p/f73dc8597db4
post-order recursion 部分:http://www.reibang.com/p/e1bbefc41237
鏈表的分治/遞歸:
- Remove Duplicates from Sorted List
- Reverse Linked List