Home

LinkedList

• DummyNode 可以避免 if null 的判斷，簡化代碼
• 雙指針／快慢指針

Linked List的复习总结

Tree

树的遍历

Key Concepts

Binary Tree遍历问题有一个关键点就是当指针走到底层以后如何返回的问题

preorder

• recursive
• iterative 需要stack, 另外可以利用更新root本身来实现遍历O(lgN)的额外空间
• Morris 不需要额外空间

inorder

• recursive
• iterative
• Morris 實作與preordr一樣，輸出順序不同

postorder

有一种省事的方法，即将preorder的方法将结果输入到一个stack中，然后反向输出即可

• recursive
• iterative 使用了两个指针来记录节点访问情况
• Morris 實作很不一樣

level order traversal

用 iterative 的方式，不過使用queue来代替stack的作用

Dynamic Programming

動態規劃(Dynamic Programming)是指將一個較大的問題定義為較小的子問題組合，先處理較小的問題並將結果儲存起來(通常使用表格)，再進一步以較小問題的解逐步建構出較大問題的解。

與其他演算法設計哲學比較

• Divide-and-Conquer：Divide-and-Conquer 和 Dynamic Programming都是將問題切割再採用遞迴方式處理子問題，但是Divide-and-Conquer子問題的解通常不會重覆，重複時，通常會對相同子問題進行重覆計算，而不會像Dynamic Programming的子問題有大量的重複(overlap)，可以以table儲存不用再次計算，用空間換取時間。
• Greedy Approach：Greedy Approach具有Selection Procedure，自某起始點開始在每一個階段逐一檢查每一個輸入是否適合加入答案中。如果所要處理的最佳化問題無法找到一個選擇程序來逐一檢查，而需要以一次考慮所有的可能情況的方式來處理，那就是屬於Dynamic Programming。因此若遇最佳化問題，先思考可否用Greedy Approach解，若不行再考慮Dynamic Programming。

Links

• Algorithm - Ch2 動態規劃 Dynamic Programming