七十九、深度和广度优先搜索算法
「@Author：Runsen」
❝编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」 ❞
深度优先搜索和广度优先搜索作为应用广泛的搜索算法，一般是必考算法。
深度优先算法（DFS）
深度优先算法的本质是回溯算法，多数是应用在树上，一个比较典型的应用就是二叉树的中序遍历。
DFS的实现考虑要以下几个问题即可：
①．边界范围：「即搜索终止条件，递归结束条件。」
②．可供选择的范围列表：「所有可供选择的范围列表。」
③．已做出的选择列表：「标记当前已经做出的选择。」
深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。
根据深度优先搜索的特点，采用递归函数实现比较简单。
广度优先算法（BFS）
先访问完当前顶点的所有邻接点，然后再访问下一层的所有节点，该算法适用于解决最短、最小路径等问题，但是构建广度优先算法需要维护自己的队列。
比如，二叉树的层次遍历，我们大概会有如下几个步骤：
- 向Queue中放入root节点。
- 只要这个Queue中有元素就一直遍历。
- 每次遍历时，首先计算一下当前Queue里有多少个元素，这就是这棵树当前层级元素的数量，记作Size。
- 接下来从Queue中移除Size中的多个元素，对他们进行符合我们题目的一些操作。
- 移除每个节点时，把它们的子节点添加进Queue中。
- 只要Queue中还有元素，说明还有下一个层级，就一直重复步骤3去处理下一个层级。
Leetcode第111题：二叉树的最小深度
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
# 说明: 叶子节点是指没有子节点的节点。
# 示例:
# 给定二叉树 [3,9,20,null,null,15,7],
# 3
# / \
# 9 20
# / \
# 15 7
#
# 返回它的最小深度 2.
# Related Topics 树 深度优先搜索 广度优先搜索
最大深度：「最大深度是从根节点到最近叶子节点的最长路径上的节点数量。」
最小深度：「最小深度是从根节点到最近叶子节点的最短路径上的节点数量。」
对于一个节点，如果是叶子节点，则返回其深度；如果只有左子树，则递归得到左子树的最小深度；如果只有右子树，则递归得到右子树的最小深度；如果左右孩子节点都有，则递归得到两个子树的深度，并且取最小值。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
return self.get_min_depth(root, 0)
def get_min_depth(self, node, depth):
# 分为四种情况：叶子节点，只有左孩子的节点，只有右孩子的节点，两个孩子都有的节点
if not node.left and not node.right:
return depth+1
if node.left and node.right:
return min(self.get_min_depth(node.left, depth+1), self.get_min_depth(node.right, depth+1))
if node.left:
return self.get_min_depth(node.left, depth+1)
if node.right:
return self.get_min_depth(node.right, depth+1)
上面的是代码是递归的做法。
广度优先算法(BFS)，当遇到第一个叶子节点的时候，该节点深度就是最小深度。
代码和层次遍历的代码很类似。
from collections import queue
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
queue = [(1, root)]
while queue:
depth, node = queue.pop(0)
if not node.left and not node.right:
return depth
if node.left:
queue.append((depth + 1, node.left))
if node.right:
queue.append((depth + 1, node.right))
return 0
首先可以想到使用深度优先搜索的方法，遍历整棵树，记录最小深度。
对于每一个非叶子节点，我们只需要分别计算其左右子树的最小叶子节点深度。这样就将一个大问题转化为了小问题，可以递归地解决该问题。
DFS，需要把所有的叶子节点的深度进行比较，才可以得到最终的最小深度。
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
min_depth = float('inf')
if root.left:
min_depth = min(self.minDepth(root.left), min_depth)
if root.right:
min_depth = min(self.minDepth(root.right), min_depth)
return min_depth + 1
Leetcode第112题：路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
# 示例:
#给定如下二叉树，以及目标和 sum = 22，
#
# 5
# / \
# 4 8
# / / \
# 11 13 4
# / \ \
# 7 2 1
# 返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
# Related Topics 树 深度优先搜索
方法一：递归（DFS，深度优先搜索）
利用 DFS 找出从根节点到叶子节点的所有路径，只要有任意一条路径的 和 等于 sum，就返回 True。
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
# 二叉树 root 为 null
if not root:
return False
# 无左右子树
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)
我们可以想到使用广度优先搜索的方式，记录从根节点到当前节点的路径和，以防止重复计算。
collection 为 Python 的内建集合版块，collection.deque 为双端队列，可以从两端添加（append）和弹出（pop）元素，且时间复杂度为 O(1)，耗时小于 list 的 insert 和 pop 操作的 O(N)。
d = deque([1, 2, 3, 4, 5]
## 两端添加元素
d.append(6) # deque([1, 2, 3, 4, 5, 6])
d.appendleft(0) # deque([0, 1, 2, 3, 4, 5, 6])
## 两端按序拓展元素
d.extend([7, 8]) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8])
d.extendleft([-1, -2]) # deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8])
## 指定位置插入元素
d.insert(0, -3) # deque([-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8])
## 两端弹出元素
d.pop() # deque([-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7])
d.popleft() # deque([-2, -1, 0, 1, 2, 3, 4, 5, 6, 7])
## 删除从左到右找到的首个指定元素
d.remove(-1) # deque([-2, 0, 1, 2, 3, 4, 5, 6, 7])
## 指定元素计数
d.count(3) # 1
## 返回从左到右找到的首个指定元素的索引
d.index(5) # 6
## 逆序排列
d.reverse() # deque([7, 6, 5, 4, 3, 2, 1, 0, -2])
## 元素双向循环指定步数
d.rotate(2) # deque([0, -2, 7, 6, 5, 4, 3, 2, 1])
d.rotate(-2) # deque([7, 6, 5, 4, 3, 2, 1, 0, -2])
时间复杂度：O(N) 空间复杂度：O(H)，H 为树的高度，最坏情况下，树成链状，为 O(N)。
import collections
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
que_node = collections.deque([root]) # 结点队列
que_val = collections.deque([root.val]) # 结点值队列
while que_node:
now = que_node.popleft() # 当前结点
temp = que_val.popleft() # 临时存储值
if not now.left and not now.right:
if temp == sum:
return True
continue
if now.left:
que_node.append(now.left)
que_val.append(now.left.val + temp)
if now.right:
que_node.append(now.right)
que_val.append(now.right.val + temp)
return False
❝本文已收录 GitHub，传送门~[1] ，里面更有大厂面试完整考点，欢迎 Star。 ❞
Reference
[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -
腾讯云开发者
