python BFS和DFS LeetCode
BFS主要用队列来实现，DFS主要用栈来实现
#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
)
#对数据进行操作，
.
.
.
for
next_node
in
node
.
children
(
)
:
if
not
next_node
in
visited
:
dfs
(
next_node
,
visited
)
#非递归写法，类似于栈的结构
def
DFS（self
.
tree
)
:
if
tree
.
root
is
None
:
return
[
]
visited
,
stack
=
{
}
,
[
tree
.
root
]
while
stack
:
node
=
stack
.
pop
(
)
visited
.
add
(
node
)
#处理数据部分
process
(
node
)
#查找子节点，或者是相互连接的节点（对于图而言）
nodes
=
generate_related_nodes
(
node
)
stack
.
push
(
nodes
)
如前文所述一样，BFS肯定是比较简单能想到的，用队列存储每一层的节点，然后一个一个的出队列，如果这个节点有孩子，那么就加入到队列中。当然也可以用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
)
