专栏首页用户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刷题】广度优先搜索(BFS)

    西西嘛呦
  • 【python刷题】回溯算法(深度优先搜索DFS)

    结果: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

    西西嘛呦
  • 优秀题解【图的遍历——深度优先搜索】

    解题思路: (1)总思路:在图中任意选取一个顶点开始(题目要求编号为0开始),访问该顶点,并把该顶点设置为已访问

    编程范 源代码公司
  • DAG的深度优先搜索标记

    这是图论的基础知识点,也是学习Tarjan的导学课。 一、知识 对于在图G上进行深度优先搜索算法所产生的深度优先森林Gt,我们可以定义四种边的类型:

    风骨散人Chiam
  • Python|DFS(深度优先搜索)介绍

    在众多算法中,时常会用到一种适用于大多数情况的方法,这就是遍历。遍历中的DFS(深度优先搜索)就是今天要介绍的。DFS有递归性结构中最重要的一些属性,一旦在某个...

    算法与编程之美
  • 迷宫问题(maze problem)——深度优先(DFS)与广度优先搜索(BFS)求解

    给定一个迷宫,指明起点和终点,找出从起点出发到终点的有效可行路径,就是迷宫问题(maze problem)。

    Dabelv
  • 算法:堆栈与深度优先搜索(迷宫问题)

    堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈顶的元素,也就是说,只能访问栈顶元素而不能...

    s1mba
  • Python 刷题笔记:位运算专题一

    学 Python 初接触 &、| 等运算符时,只大概了解它们被称为位运算符,并不同于逻辑运算符 and、or,今天就通过基础知识点和几道题目来熟悉下。

    TTTEED
  • Python 刷题笔记:位运算专题二

    正数三码相同,负数的反码才会除了首位符号位不变、其余位取反。位运算都是基于数字的补码来进行运算的。

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

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

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

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

    TTTEED
  • Python 刷题笔记:贪心算法专题一

    LeetCode 每月都会搞每日一题活动,昨天的题目是贪心算法类型,折腾好久才做出来,索性今天就围绕贪心算法多看几道。

    TTTEED
  • Python 刷题笔记:贪心算法专题二

    最近我们开始练习贪心算法的题目,昨天因为卡在其中一道简单级别的题目上没能更新,今天补更,正好也借着卡的点分享下经验。关于贪心算法的介绍,如果想回顾,可以点上篇来...

    TTTEED
  • Python 刷题笔记:贪心算法专题三

    今天仍旧是贪心算法的题目,加上之前两篇的四道题,对贪心算法的应用也大致有些印象了,明天换个其它类型题目来继续刷。

    TTTEED
  • 【优秀题解】问题 1703: 图的遍历——广度优先搜索

    2):广度优先遍历相当于树的层次遍历:选取图中任意一个顶点开始遍历,然遍历该节点的所有未被访问的边表节点,再把访问了的边表节点入队列,出队列一个节点,循环上述过...

    编程范 源代码公司
  • Leetcode 78. Subsets Python DFS 深度优先搜索解法

    Given a set of distinct integers, nums, return all possible subsets (the power s...

    大鹅
  • 知识体系、算法题、教程、面经,这是一份超赞的AI资源列表

    照例先放上 GitHub 地址:https://github.com/Awesome-Interview/Awesome-Interview#LeetCode,...

    CDA数据分析师
  • 知识体系、算法题、教程、面经,这是一份超赞的AI资源列表

    照例先放上 GitHub 地址:https://github.com/Awesome-Interview/Awesome-Interview#LeetCode,...

    AI科技大本营

扫码关注云+社区

领取腾讯云代金券