专栏首页用户6811391的专栏Python 刷题笔记:深度优先搜索专题

Python 刷题笔记:深度优先搜索专题

今天来接触下专业术语——深度优先搜索算法(英语:Depth-First-Search,DFS)

❝深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。 深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如最大路径问题等等。 链接:https://leetcode-cn.com/tag/depth-first-search/ ❞

这里提到,该算法多用于遍历或搜索树或图,那么以二叉树为例,该算法即尽可能的从根节点向下直到叶节点才结束,到达叶节点后再由根节点重新向下延伸。

但是,怎么实现在我们到达叶节点时回到根节点来重新开始呢?初接触,我的理解是通过递归来实现。在对根节点的函数中调用关于其子节点的函数,以此建立父子间的关联;同时其子节点不止一个的话,那么所谓的回溯其实也就通过递归同步实现了。

举三道 LeetCode 题目为例,看看它们是如何实现深度优先搜索的吧!

题目一

「第 100 题:相同的树」

难度:简单

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:
输入:       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

示例 2:
输入:      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
输出: false

示例 3:
输入:       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
输出: false

#来源:力扣(LeetCode)
#链接:https://leetcode-cn.com/problems/same-tree

题目分析

既然要深度优先搜索,那么要从根节点起一直到不能再向下子节点为止,这么产生一条链;比较两个二叉树相同,那么只要保证生成这条链的过程中每个节点都是相同的即可。

思路很简单,到代码怎么实现呢?因为这题目是检测两棵二叉树是否相同,自然会定义检测函数。二叉树是由根节点和子树组成的,检测两棵二叉树是否相同,我们保证根节点相同的情况下,检查子树是否相同即可——注意,检查子树,又可以调用我们定义的检测函数,以此形成递归用法,这样通过递归便可实现深度优先搜索了。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 两根节点均为空,返回 True
        if p is None  and q is None:
            return True
        # 其中一个空、另一个非空,返回 False
        elif p is None or q is None:
            return False
        # 两根节点均非空时,若根节点值不同,返回 False
        if p.val != q.val:
            return False
    # 若根节点相同,比较两个左子树以及两个右子树是否都相同
    # 递归对相应的子节点调用函数本身
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

提交测试表现:

执行用时 : 36 ms, 在所有 Python3 提交中击败了 80.96% 的用户
内存消耗 : 13.5 MB, 在所有 Python3 提交中击败了 7.14% 的用户

题目二

「第 101 题:对称二叉树」

难度:简单

给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

题目分析

如果不用深度优先搜索,可以考虑层序遍历,但即使是空子节点,也要遍历记录,这样来检测每层的节点列表是否对称即可。

但倘若采用深度优先搜索,与比较两棵树是否相同类似,我们要设计下如何复用设计的函数来通过子节点来继续比较是否对称。

本题中我们只输入一个根节点、一棵完整的树,但检查其是否对称,则要根据其子树是否对称。在检查子树是否对称的过程中,子树的根节点位置是要相等的,再下层的子树又要继续与对应位置上的子树对称,这样我们便可以通过检测两棵子树是否对称的函数实现递归。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 如果根节点为空,返回 True
        if not root:
            return True
        # 自定义检测子节点是否对称
        def check_sym(node1,node2):
            # 若两节点均空,返回 True
            if node1 is None and node2 is None:
                return True
            # 若一空一非空,返回 False
            elif node1 is None or node2 is None:
                return False
            # 两子节点作为对称点,若不等,返回 False
            if node1.val!=node2.val:
                return False
            # 继续寻找子节点下面的对称节点,形成递归
            return check_sym(node1.left,node2.right) and check_sym(node1.right,node2.left)
        # 对左右子节点
        return check_sym(root.left,root.right)

提交测试表现:

执行用时 : 52 ms, 在所有 Python3 提交中击败了 29.42% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 6.06% 的用户

试着加一下复杂度分析:因为我们是遍历整个二叉树一次,共 n 个节点,故时间复杂度为 O(n);空间上,运气好的话可能不用每层都检测完找到不对称就返回,但对称的话则需要对所有节点进行递归调用,造成的空间复杂度为 O(n)。

题目三

「第 104 题:二叉树的最大深度」

难度:简单

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

「示例:」

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

题目分析

根节点对应左右两棵子树,二叉树高度为大的子树高度再加一,那么子树高度又可以递归地等于其更大的子树高度加一,就这样递归形成。

代码实现

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 空节点返回高度 0
        if not root:
            return 0
        # 当前树高度为较大的子树高度+1
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

提交测试表现:

执行用时 : 40 ms, 在所有 Python3 提交中击败了 97.63% 的用户
内存消耗 : 15.5 MB, 在所有 Python3 提交中击败了 5.55% 的用户

这个时间比例并不准确,差几 ms 比例却差得很多。为了计算每个子树的高度来比较,n 个节点都会被遍历到,故时间复杂度 O(n);递归也将被调用 n 次,保持调用栈的存储是 O(n)。

结论

明明昨天结束了二叉树题型的,结果今天由于算法的特性三道题目又都是二叉树的。在学习和理解这算法的过程中,对深度优先搜索可能只是概念上增强,反倒对递归的应用更熟练了。

简单整理下深度优先搜索的思路,由根节点向叶节点的过程中,找到可以复用的函数来实现递归过程,这样便非常省力地通过递归来实现由上到下的联系,以达到深度搜索的效果。

为了快速学习,今天选取的都是简单题目,之后还是不同难度搭配着来比较好些。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 刷题笔记:广度优先搜索专题

    昨天看过了简单题汇聚的深度优先搜索专题,今天来体验下简单级别的广度优先搜索专题。老样子,先熟悉下术语概念:

    TTTEED
  • Python 刷题笔记:二叉树专题一

    今天来看二叉树专题,首先我们先整理下基础知识点;基于在 LeetCode 推荐题解中发现的一个适用于二叉树遍历的套路解法,我们今天也会连刷三道关于前序、中序和后...

    TTTEED
  • Python 刷题笔记:二叉树专题二

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

    TTTEED
  • Kubernetes调度器101

    如果你阅读过Kubernetes的任何文档、书籍或文章,那么毫无疑问,你会在“Pod被调度到下一个可用节点”之类的短语中看到调度“schedule”这个词。Ku...

    CNCF
  • python 实现二叉树的深度 & 广度优先遍历

    前面说到算法被虐了,这回我要好好把它啃下来。哪里跌倒就要从哪里站起来。这是我复习算法与数据结构时的小笔记,这里就 po 出来,给大家也复习一下旧的知识点,查缺补...

    小小詹同学
  • 图论与图学习(二):图算法

    本文是其中第二篇,介绍了图算法。更多文章和对应代码可访问:https://github.com/maelfabien/Machine_Learning_Tuto...

    机器之心
  • 算法与数据结构(六):堆排序

    上一次说到了3种基本的排序算法,三种基本的排序算法时间复杂度都是O(n^2),虽然比较简单,但是效率相对较差,因此后续有许多相应的改进算法,这次主要说说堆排序算...

    Masimaro
  • leetcode331. Verify Preorder Serialization of a Binary Tree

    我们知道,任何两个节点都可以和位于左边的非叶节点构成一棵有三个节点的树。如果我们从右往左看先序遍历,就知道后两个节点如果遇到第三个节点,则该节点就应当是这两个节...

    眯眯眼的猫头鹰
  • 重温数据结构:深入理解红黑树

    读完本文你将了解到: 什么是红黑树 黑色高度 红黑树的 5 个特性 红黑树的左旋右旋 指定节点 x 的左旋 右图转成左图 指定节点 y 的右旋左图转成右图 红...

    张拭心 shixinzhang
  • 算法数据结构(一)-B树

    蘑菇先生

扫码关注云+社区

领取腾讯云代金券