BFS vs DFS

找最短路徑用BFS, 其他時用DFS用得多一些, 因為遞迴較好寫

假設有棵滿的二叉樹,節點數為 N. 對DFS來說空間複雜度就是遞迴, 最壞的情況就是樹的高度 O(log N) BFS算法, Queue每次都會存二叉樹一層的節點,最壞的情況下空間複雜度應該就是樹的最下層的數量, 也就是 N/2. 空間複雜度 O(N)

DFS

• 回溯算法 (Backtracking)
• DFS 也可以找到最短路徑, 時間複雜度一樣式O(n). 但實際效能比 BFS 低很多. 因為 DFS 靠遞迴方式記錄走過的路徑, 要找到最後路徑, 需要把整顆樹走完, 然後才比對出最段路徑; BFS 藉由 Queue 一步一步齊頭並進, 可以在樹還沒走完時找到最短路徑. 雖然兩者最壞的時間複雜度都相等, 但實際 BFS效能較好

BFS

• Queue
• BFS 找到的路徑一定是最短的, 代價是空間複雜度比 DFS 大很多

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0310.Minimum-Height-Trees/main.go