給定一個(gè)二叉樹芥牌，找出其最大深度。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)厘线。
說明: 葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)奄毡。
示例：
給定二叉樹 [3,9,20,null,null,15,7]
?? 3
? / ?\
9 ??20
??/ ??\
? 15 ?7
返回它的最大深度 3 鸦做。
解法 1
DFS励烦，利用深度優(yōu)先搜索，遍歷二叉樹的每條路徑泼诱，若當(dāng)前節(jié)點(diǎn)不為空坛掠，則判斷左子樹和右子樹的深度，返回其中最大的子樹深度并加上 1（當(dāng)前節(jié)點(diǎn)）治筒。若當(dāng)前節(jié)點(diǎn)為空則返回 0屉栓。由所有葉子節(jié)點(diǎn)回溯到根節(jié)點(diǎn)時(shí)，即可計(jì)算出二叉樹最大深度矢炼。
def max_depth(root):
if not root:
return 0
return max(max_depth(root.left), max_depth(root.right)) + 1
執(zhí)行用時(shí) :48 ms
內(nèi)存消耗 :14.6 MB
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：在最糟糕的情況下系瓢，樹是完全不平衡的，例如每個(gè)結(jié)點(diǎn)只剩下左子結(jié)點(diǎn)句灌，遞歸將會(huì)被調(diào)用 n 次（樹的高度）夷陋，因此保持調(diào)用棧的存儲(chǔ)將是 O(n)。但在最好的情況下（樹是完全平衡的）胰锌，樹的高度將是 log(n)骗绕。因此，在這種情況下的空間復(fù)雜度將是 O(log(n))资昧。
解法 2
BFS酬土，利用廣度優(yōu)先搜索，遍歷二叉樹的每一層格带，如果當(dāng)前節(jié)點(diǎn)是葉子節(jié)點(diǎn)撤缴，那么當(dāng)前層級(jí)數(shù)即為該葉子節(jié)點(diǎn)深度刹枉。如果當(dāng)前葉子節(jié)點(diǎn)深度大于最大深度，則更新最大深度屈呕。
def max_depth(root):
stack = []
depth = 0
if root is not None:
stack.append((1, root))
while stack:
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return depth
執(zhí)行用時(shí) :40 ms
內(nèi)存消耗 :14.2 MB
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
如果是求最小深度呢微宝？
解法 1
DFS，和求最大深度一樣虎眨，遍歷二叉樹的每條路徑蟋软。需要注意的是，當(dāng)某個(gè)子樹為空時(shí)嗽桩，還需要計(jì)算另一個(gè)非空子樹的深度岳守，兩個(gè)子樹都為空的節(jié)點(diǎn)才是葉子節(jié)點(diǎn)。
def min_depth(root):
if not root:
return 0
if not root.left:
return min_depth(root.right) + 1
if not root.right:
return min_depth(root.left) + 1
return min(min_depth(root.left), min_depth(root.right)) + 1
執(zhí)行用時(shí) :44 ms
內(nèi)存消耗 :14.8 MB
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)
解法 2
BSF碌冶，和最大深度一樣湿痢，遍歷二叉樹的每一層，需要注意的是扑庞，這里利用隊(duì)列先進(jìn)先出的特性來存儲(chǔ)節(jié)點(diǎn)蒙袍，并進(jìn)行層次遍歷，第一個(gè)子節(jié)點(diǎn)的層級(jí)深度即為最小深度嫩挤。
def min_depth(root):
if not root:
return 0
else:
node_deque = deque([(1, root), ])
while node_deque:
depth, root = node_deque.popleft()
children = [root.left, root.right]
if not any(children):
return depth
for c in children:
if c:
node_deque.append((depth + 1, c))
執(zhí)行用時(shí) :44 ms
內(nèi)存消耗 :14.3 MB
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)，最壞的情況要遍歷到最后一層
參考
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
