python 最大深度最小深度 LeetCode 104，111
解法：
1、BFS：尋找最大深度的時候，很容易想到就是，可以直接進行層次遍歷，當無法在進行遍歷下去的時候就是最深的深度；當尋找最小深度的時候，對每一個節點檢查它是否是葉子節點，也就是檢查它是否有左子樹和右子樹。
2、DFS：每次進行遍歷的時候，要判斷是否是葉子節點，更新max深度的值和min深度的值。
BFS版本
# 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
maxDepth
(
self
,
root
)
:
"""
:type root: TreeNode
:rtype: int
"""
if
not
root
:
return
0
if
not
root
.
right
and
not
root
.
left
:
return
1
cur
=
[
root
]
maxnum
=
0
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
maxnum
+=
1
return
maxnum
# 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
if
not
root
.
right
and
not
root
.
left
:
return
1
cur
=
[
root
]
minnmb
=
0
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
)
for
node
in
cur
:
if
not
node
.
left
and
not
node
.
right
:
minnmb
+=
1
return
minnmb
if
node
==
cur
[
-
1
]
:
minnmb
+=
1
cur
=
nextstack
上面的代碼居然提交，打敗了99.89的人，我？？？？黑人問號！??！記錄以下～～
DFS版本
# 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
maxDepth
(
self
,
root
)
:
"""
:type root: TreeNode
:rtype: int
"""
if
not
root
:
return
0
return
1
+
max
(
self
.
maxDepth
(
root
.
right
)
,
self
.
maxDepth
(
root
.
left
)
)
# 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
if
not
root
.
left
:
return
1
+
self
.
minDepth
(
root
.
right
)
if
not
root
.
right
:
return
1
+
self
.
minDepth
(
root
.
left
)
return
1
+
min
(
self
.
minDepth
(
root
.
right
)
,
self
.
minDepth
(
root
.
left
)
)
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
