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
)
)
