七十九、深度和广度优先搜索算法

「@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