python BFS和DFS LeetCode
BFS主要用隊列來實現(xiàn)，DFS主要用棧來實現(xiàn)
#BFS模版
def
BFS
(
graph
,
start
,
end
)
:
visited
,
quene
=
set
(
)
,
[
start
]
visited
.
add
(
start
)
while
queue
:
node
=
quenue
.
pop
(
)
visited
.
add
(
node
)
process
(
node
)
nodes
=
generate_related_nodes
(
node
)
queuq
.
push
(
nodes
)
#DFS不完全代碼，用于面試模版，遞歸寫法
visited
=
set
(
)
def
dfs
(
node
,
visited
)
:
visited
.
add
(
node
)
#對數(shù)據(jù)進(jìn)行操作，
.
.
.
for
next_node
in
node
.
children
(
)
:
if
not
next_node
in
visited
:
dfs
(
next_node
,
visited
)
#非遞歸寫法，類似于棧的結(jié)構(gòu)
def
DFS（self
.
tree
)
:
if
tree
.
root
is
None
:
return
[
]
visited
,
stack
=
{
}
,
[
tree
.
root
]
while
stack
:
node
=
stack
.
pop
(
)
visited
.
add
(
node
)
#處理數(shù)據(jù)部分
process
(
node
)
#查找子節(jié)點，或者是相互連接的節(jié)點（對于圖而言）
nodes
=
generate_related_nodes
(
node
)
stack
.
push
(
nodes
)
如前文所述一樣，BFS肯定是比較簡單能想到的，用隊列存儲每一層的節(jié)點，然后一個一個的出隊列，如果這個節(jié)點有孩子，那么就加入到隊列中。當(dāng)然也可以用DFS，DFS可以讓面試官眼前一臉。
class
Solution
(
object
)
:
def
levelOrder
(
self
,
root
)
:
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if
not
root
:
return
root
if
not
root
.
left
and
not
root
.
right
:
return
[
[
root
.
val
]
]
cur
=
[
root
]
res
=
[
]
while
cur
:
nextStack
,
tmp
=
[
]
,
[
]
for
node
in
cur
:
tmp
.
append
(
node
.
val
)
if
node
.
left
:
nextStack
.
append
(
node
.
left
)
if
node
.
right
:
nextStack
.
append
(
node
.
right
)
cur
=
nextStack
res
.
append
(
tmp
)
return
res
# 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
levelOrder
(
self
,
root
)
:
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if
not
root
:
return
[
]
result
=
[
]
queue
=
collections
.
deque
(
)
queue
.
append
(
root
)
# visited = set(root)
while
queue
:
level_size
=
len
(
queue
)
current_level
=
[
]
for
_
in
range
(
level_size
)
:
node
=
queue
.
popleft
(
)
current_level
.
append
(
node
.
val
)
if
node
.
left
:
queue
.
append
(
node
.
left
)
if
node
.
right
:
queue
.
append
(
node
.
right
)
result
.
append
(
current_level
)
return
result
# 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
levelOrder
(
self
,
root
)
:
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if
not
root
:
return
[
]
self
.
result
=
[
]
self
.
_dfs
(
root
,
0
)
return
self
.
result
def
_dfs
(
self
,
node
,
level
)
:
if
not
node
:
return
if
len
(
self
.
result
)
<
level
+
1
:
self
.
result
.
append
(
[
]
)
self
.
result
[
level
]
.
append
(
node
.
val
)
self
.
_dfs
(
node
.
left
,
level
+
1
)
self
.
_dfs
(
node
.
right
,
level
+
1
)
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
