n種解法破DFS與BFS
- 2019 年 10 月 5 日
- 筆記
n種解法破DFS與BFS
0.說在前面1.二叉樹的層次遍歷I1.1 BFS非遞歸思路11.2 BFS非遞歸思路21.3 BFS雙端隊列1.4 BFS遞歸思路1.5 DFS遞歸思路2.二叉樹的層次遍歷II2.1 反轉思路2.2 直接插入
0.說在前面
最近實在太忙了，但是算法我時刻不會忘記，每周都刷至少兩道，比如我昨天上課無聊，拿手機刷了兩道，感覺很easy，或許我刷的比較簡答吧，然後今天回到實驗室，看了之前給Datawhale編程實踐定的任務，是一道層次遍歷，於是這道題引發了我的思考，剛好晚上有時間，就花了時間來研究一波，結果真的很有趣。
一件事，簡單而又直白；一件事，複雜而又晦澀；我寧願選擇後者，因為他可以激發你的潛能！
今天呢主要來介紹兩道題，二叉樹的層次遍歷I與II，運用的思想為DFS與BFS，實現算法包含遞歸與非遞歸！
1.二叉樹的層次遍歷I
關於DFS與BFS這裡不多做介紹，會在後面寫出幾篇簡單文章讓大家來看，如果有什麼需求，可以留言！
【問題】
給定一個二叉樹，返回其按層次遍歷的節點值。 （即逐層地，從左到右訪問所有節點）。
例如: 給定二叉樹: [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回其層次遍歷結果：
[ [3], [9,20], [15,7] ]
1.1 BFS非遞歸思路1
【思路】
採用傳統的隊列思路，先入先出思想，層次遍歷大家都知道吧，就是一行訪問完畢，再訪問下一行，很有順序，而對於二叉樹BFS與層次遍歷一致，那麼這裡就是採用BFS隊列的思路來操作！
【實現】
代碼實現思路為：首先對特殊情況處理，然後定義一個queue(用來存放每層節點)及結果list。然後進入循環，再次建立一個空的list用來存放每層的節點值，然後對queue循環出隊，對出隊的節點操作(讓左孩子與右孩子入隊)，所以在代碼中引入了同層節點個數的變量length，主要是queue要做修改，所以會發生改變，自然不能直接遍歷原先的queue！每層訪問完畢，讓這層的節點值list添加到結果list中，返回即可！
def levelOrder(self, root): res = [] if root is None: return res queue = [root] # 列表為空時，循環終止 # 可以省去len(queue)!=0 while queue and len(queue) != 0: # 使用列表存儲同層節點 level_val = [] # 同層節點的個數 length = len(queue) for i in range(length): # 將同層節點依次出隊 h = queue.pop(0) if h.left: # 左孩子入隊 queue.append(h.left) if h.right: # 右孩子入隊 queue.append(h.right) level_val.append(h.val) res.append(level_val) return res
1.2 BFS非遞歸思路2
【思路】
這個思路與上面類似，不同之處在於，這裡在循環裏面建立了兩個list，而這兩個list的作用分別為，一個用來存儲每層節點值，一個用來存儲每層的左右孩子節點，其實思路1與2基本一致，只是代碼風格不一樣，建議採用第一種思路寫！
【實現】
def levelOrder(self, root): res = [] if not root: return [] res_list = [] root_list = [root] while root_list and len(root_list)!=0: # 每層節點值 val_list = [] # 每層左右孩子節點 level_list = [] for node in root_list: val_list.append(node.val) if node.left: level_list.append(node.left) if node.right: level_list.append(node.right) # 修改循環條件 root_list = level_list # 結果集中添加每層list res_list.append(val_list) return res_list
1.3 BFS雙端隊列
【思路】
思路同上1
【實現】
實現思路：採用了collections裏面的雙端隊列deque!具體的用法注釋標出了！
def levelOrder(self, root): res = [] if not root: return res # 導包 import collections # 雙端隊列定義 queue = collections.deque() queue.append(root) # visited = set(root) while queue: length = len(queue) level_val = [] for _ in range(length): # 彈出最左邊的節點 node = queue.popleft() level_val.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level_val) return res
1.4 BFS遞歸思路
【思路】
思路就是遞歸+BFS，具體思路看實現！
【實現】
首先在結果list中每層插入一個空list，然後循環每一層所有節點，將當前節點直接加入對應層當中，然後更新下一層節點list(更新方法為：將當前及節點的左右孩子入list即可)，然後不斷遞歸，直到下一層沒有節點了，結束遞歸！
所以這裡是一層層遞歸，一層層實現，所以名字為BFS遞歸！
def levelOrder(self, root): if root is None: return [] self.res = [] self.bfs([root], 0) return self.res def bfs(self, level_nodes, level): if not level_nodes: return self.res.insert(level, []) temp = [] for node in level_nodes: self.res[level].append(node.val) if node.left: temp.append(node.left) if node.right: temp.append(node.right) self.bfs(temp, level+1)
1.5 DFS遞歸思路
【思路】
思路就是採用深度優先搜索，先選擇一個分支不斷往下遍歷，標記訪問過的節點，在去繼續往下，如果已經到達終點，回退各個分支節點，進入下一分支，重複前面步驟，直到所有節點訪問完畢！
【實現】
在代碼中體現深度優先搜索的為：
self.result[level].append(root.val)
這一行表示為當前層添加節點值！
具體的解釋放在注釋中！
def levelOrder(self, root): # 特殊情況處理 if not root: return [] # 定義結果list self.result = [] # 調用函數 self.dfs(root, 0) # 返回結果 return self.result # dfs函數 def dfs(self, root, level): # 這一行很關鍵，主要是用來為訪問下一層的節點添加一個空的list if len(self.result) < level + 1: self.result.append([]) # 訪問對應level的list，並添加數據 self.result[level].append(root.val) # 左孩子遞歸 if root.left: self.dfs(root.left, level + 1) # 右孩子遞歸 if root.right: self.dfs(root.right, level + 1)
對於上述的dfs遞歸的終止條件就是，沒有左右孩子了，就結束了，為了更加好看，可以寫成如下代碼：
改寫變動為終止條件變動及左右孩子訪問判斷條件變動！
def dfs(self, root, level): # 遞歸終止條件 if not root: return # 這一行很關鍵，主要是用來為訪問下一層的節點添加一個空的list if len(self.result) < level + 1: self.result.append([]) # 訪問對應level的list，並添加數據 self.result[level].append(root.val) # 左孩子遞歸 self.dfs(root.left, level + 1) # 右孩子遞歸 self.dfs(root.right, level + 1)
2.二叉樹的層次遍歷II
上面介紹了5種方法解決二叉樹的層次遍歷！那麼下面又有一道題是對上面的簡單處理，下面接着來看！
【問題】
給定一個二叉樹，返回其節點值自底向上的層次遍歷。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）
例如： 給定二叉樹 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7
返回其自底向上的層次遍歷為：
[ [15,7], [9,20], [3] ]
2.1 反轉思路
反轉思路為將一個list直接做反轉即可，實現為：
list[::-1]
所以將上面的所有方法最後返回結果直接跟個[::-1]，那麼這道題就解決了！
2.2 直接插入
上面最後需要做反轉，也就是切片，這樣的話時間複雜度會變高，有沒有更高效率了，當然有了，那就是直接插入了！
怎麼改呢？
直接將上面的結果list的append改為insert(0,xxx)，就是在每次數據的前面插入，這樣就保證的先入的在棧底！也就滿足了題意！
