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