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