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)。
结论
明明昨天结束了二叉树题型的，结果今天由于算法的特性三道题目又都是二叉树的。在学习和理解这算法的过程中，对深度优先搜索可能只是概念上增强，反倒对递归的应用更熟练了。
简单整理下深度优先搜索的思路，由根节点向叶节点的过程中，找到可以复用的函数来实现递归过程，这样便非常省力地通过递归来实现由上到下的联系，以达到深度搜索的效果。
为了快速学习，今天选取的都是简单题目，之后还是不同难度搭配着来比较好些。