七十九、深度和廣度優(yōu)先搜索算法

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

深度優(yōu)先搜索和廣度優(yōu)先搜索作為應(yīng)用廣泛的搜索算法，一般是必考算法。

深度優(yōu)先算法（DFS）

深度優(yōu)先算法的本質(zhì)是回溯算法，多數(shù)是應(yīng)用在樹上，一個比較典型的應(yīng)用就是二叉樹的中序遍歷。

DFS的實現(xiàn)考慮要以下幾個問題即可：

①．邊界范圍：「即搜索終止條件，遞歸結(jié)束條件?！?/strong>

②．可供選擇的范圍列表：「所有可供選擇的范圍列表?！?/strong>

③．已做出的選擇列表：「標(biāo)記當(dāng)前已經(jīng)做出的選擇?！?/strong>

深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮?，利用拓?fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題，如最大路徑問題等等。一般用堆數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)DFS算法。

根據(jù)深度優(yōu)先搜索的特點，采用遞歸函數(shù)實現(xiàn)比較簡單。

廣度優(yōu)先算法（BFS）

先訪問完當(dāng)前頂點的所有鄰接點，然后再訪問下一層的所有節(jié)點，該算法適用于解決最短、最小路徑等問題，但是構(gòu)建廣度優(yōu)先算法需要維護(hù)自己的隊列。

比如，二叉樹的層次遍歷，我們大概會有如下幾個步驟：

• 向Queue中放入root節(jié)點。
• 只要這個Queue中有元素就一直遍歷。
• 每次遍歷時，首先計算一下當(dāng)前Queue里有多少個元素，這就是這棵樹當(dāng)前層級元素的數(shù)量，記作Size。
• 接下來從Queue中移除Size中的多個元素，對他們進(jìn)行符合我們題目的一些操作。
• 移除每個節(jié)點時，把它們的子節(jié)點添加進(jìn)Queue中。
• 只要Queue中還有元素，說明還有下一個層級，就一直重復(fù)步驟3去處理下一個層級。

Leetcode第111題：二叉樹的最小深度

給定一個二叉樹，找出其最小深度。最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。

#?說明:?葉子節(jié)點是指沒有子節(jié)點的節(jié)點。?
#?示例:?
#?給定二叉樹?[3,9,20,null,null,15,7],?
#?????3
#???/?\
#??9??20
#????/??\
#???15???7?
#
#?返回它的最小深度?2.?
#?Related?Topics?樹?深度優(yōu)先搜索?廣度優(yōu)先搜索

最大深度：「最大深度是從根節(jié)點到最近葉子節(jié)點的最長路徑上的節(jié)點數(shù)量。」

最小深度：「最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量?！?/strong>

對于一個節(jié)點，如果是葉子節(jié)點，則返回其深度；如果只有左子樹，則遞歸得到左子樹的最小深度；如果只有右子樹，則遞歸得到右子樹的最小深度；如果左右孩子節(jié)點都有，則遞歸得到兩個子樹的深度，并且取最小值。

#?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):
????????#?分為四種情況：葉子節(jié)點，只有左孩子的節(jié)點，只有右孩子的節(jié)點，兩個孩子都有的節(jié)點
????????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)

上面的是代碼是遞歸的做法。

廣度優(yōu)先算法(BFS)，當(dāng)遇到第一個葉子節(jié)點的時候，該節(jié)點深度就是最小深度。

代碼和層次遍歷的代碼很類似。

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

首先可以想到使用深度優(yōu)先搜索的方法，遍歷整棵樹，記錄最小深度。

對于每一個非葉子節(jié)點，我們只需要分別計算其左右子樹的最小葉子節(jié)點深度。這樣就將一個大問題轉(zhuǎn)化為了小問題，可以遞歸地解決該問題。

DFS，需要把所有的葉子節(jié)點的深度進(jìn)行比較，才可以得到最終的最小深度。

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題：路徑總和

給定一個二叉樹和一個目標(biāo)和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑，這條路徑上所有節(jié)點值相加等于目標(biāo)和。

#?示例:?
#給定如下二叉樹，以及目標(biāo)和?sum?=?22，?
#
#???????????????5
#?????????????/?\
#????????????4???8
#???????????/???/?\
#??????????11??13??4
#?????????/??\??????\
#????????7????2??????1
#?返回 true, 因為存在目標(biāo)和為 22 的根節(jié)點到葉子節(jié)點的路徑 5->4->11->2。?
#?Related?Topics?樹?深度優(yōu)先搜索

方法一：遞歸（DFS，深度優(yōu)先搜索）

利用 DFS 找出從根節(jié)點到葉子節(jié)點的所有路徑，只要有任意一條路徑的 和 等于 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)

我們可以想到使用廣度優(yōu)先搜索的方式，記錄從根節(jié)點到當(dāng)前節(jié)點的路徑和，以防止重復(fù)計算。

collection 為 Python 的內(nèi)建集合版塊，collection.deque 為雙端隊列，可以從兩端添加（append）和彈出（pop）元素，且時間復(fù)雜度為 O(1)，耗時小于 list 的 insert 和 pop 操作的 O(N)。

d?=?deque([1,?2,?3,?4,?5]
##?兩端添加元素
d.append(6)?????????????????#?deque([1,?2,?3,?4,?5,?6])
d.appendleft(0)?????????????#?deque([0,?1,?2,?3,?4,?5,?6])
##?兩端按序拓展元素
d.extend([7,?8])????????????#?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])
##?指定元素計數(shù)
d.count(3)??????????????????#?1
##?返回從左到右找到的首個指定元素的索引
d.index(5)??????????????????#?6
##?逆序排列
d.reverse()?????????????????#?deque([7,?6,?5,?4,?3,?2,?1,?0,?-2])
##?元素雙向循環(huán)指定步數(shù)
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])

時間復(fù)雜度：O(N) 空間復(fù)雜度：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])????????#?結(jié)點隊列
????????que_val?=?collections.deque([root.val])?????#?結(jié)點值隊列
????????while?que_node:
????????????now?=?que_node.popleft()????????????????#?當(dāng)前結(jié)點
????????????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。

?