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

Python之王

共 5815字,需浏览 12分钟

 ·

2021-01-12 23:08


「@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([12345]
## 两端添加元素
d.append(6)                 # deque([1, 2, 3, 4, 5, 6])
d.appendleft(0)             # deque([0, 1, 2, 3, 4, 5, 6])
## 两端按序拓展元素
d.extend([78])            # 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 -

浏览 29
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报