深度优先搜索

概念

深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

具体而言

步骤1

在这里插入图片描述
A为起点，G为终点。一开始我们在起点A上。

步骤2

在这里插入图片描述
将可以从A直达的三个顶点B、C、D设为下一步的候补顶点。

步骤3

在这里插入图片描述
从候补顶点中选出一个顶点。优先选择最新成为候补的点，如果几个顶点同时成为候补，那么可以从中随意选择一个。

步骤4

在这里插入图片描述
此处B、C、D同时成为候补，所以我们随机选择了最左边的顶点。

步骤5

在这里插入图片描述
移动到选中的顶点B。此时我们在B上，所以B变为红色，同时将已经搜索过的顶点变为橙色。

步骤6

在这里插入图片描述
将可以从B直达的两个顶点E和F设为候补顶点。

步骤7

在这里插入图片描述
此时，最新成为候补顶点的是E和F，我们选择了左边的顶点E。

步骤8

在这里插入图片描述
移动到选中的顶点E上。

步骤9

在这里插入图片描述
将可以从E直达的顶点K设为候补顶点。

步骤10

在这里插入图片描述
重复上述操作直到到达终点，或者所有顶点都被遍历为止。

步骤11

在这里插入图片描述
这个示例的搜索顺序为A、B、E、K、F、C、H。

步骤12

在这里插入图片描述
现在我们搜索到了顶点C。

步骤13

在这里插入图片描述
到达终点G，搜索结束。

广度优先搜索与深度优先搜索的区别

广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。

代码

题目

剑指offer55_二叉树的深度
题目描述：
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：

给定二叉树 [3,9,20,null,null,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):if root is None: return 0 else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right) return max(left_height, right_height) + 1