Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。
透過此篇你可以學習到什麼？
詳解三種 binary tree 的走訪，並且以遞迴或非遞迴的方式實現。
分類: Leetcode
時間複雜度 – 陪你刷題
為什麼要學 Big O
學習演算法和資料結構就是為了寫出高效率的程式碼，不只在時間上需要快速，在空間上的消耗更要節省，而 Big O 就是用來衡量演算法效率的單位。因此，在學習各種資料結構與演算法帶來的好處之前，要先懂得如何透過 Big O 辨別程式碼的效率。
Backtracking 回溯法 – 陪你刷題
Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。
何謂回溯法
回溯法的處理方式就像窮舉法，將所有可能的路徑都窮舉出來，接著每條岔路都派人走下去，換個角度來看，其實這個過程就如同在決策樹或是多子樹上遍歷 (Tree Traversal) 。
但如果把每條路都確實走過，這樣的作法的時間複雜度相當高，所以回溯法有時可以使用剪枝 (pruning) 的技巧提高效率，不用將所有解法都窮舉出來。
回溯法大部份用來解決廣義的搜索問題，從許多可能的解中找出滿足要求的所有解，回溯法可以應用於以下類型:
- 八皇后問題
- DFS : DFS 也是 Backtracking 的一種型態，但 DFS 更強調搜尋的順序是以深度優先。
- 排列組合
- 0-1 背包問題