题目
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
思路
BFS广度优先搜索，使用双端队列deque（因为性能比另外两种Queue好得多），在大循环内对二叉树的每个层做一次遍历，range(len(queue))使只遍历当前的层，每次大循环ans加1。由于每个节点仅访问一次，所以时间复杂度O(n)
代码
import
collections
class
Solution
:
def
maxDepth
(
self
,
root
:
TreeNode
)
-
>
int
:
if
not
root
:
return
0
queue
=
collections
.
deque
(
)
queue
.
append
(
root
)
ans
=
0
while
queue
:
ans
+=
1
for
_
in
range
(
len
(
queue
)
)
:
node
=
queue
.
popleft
(
)
if
node
.
left
:
queue
.
append
(
node
.
left
)
if
node
.
right
:
queue
.
append
(
node
.
right
)
return
ans
