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)，就是在每次数据的前面插入，这样就保证的先入的在栈底！也就满足了题意！
