題目
給定一個(gè)二叉樹，找出其最大深度卿堂。
難度：★★☆☆☆
類型：二叉樹
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(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：遞歸法
遞歸法通過遍歷所有結(jié)點(diǎn)尋找最大深度，時(shí)間復(fù)雜度為N陶珠。我們編寫函數(shù)挟裂，確定以root為根結(jié)點(diǎn)的一棵樹的最大深度這樣：
如果根結(jié)點(diǎn)root為空，則直接返回0揍诽；
如果不為空诀蓉，則是左子樹的最大深度d1和右子樹的最大深度d2中較大的值加1。
左子樹或右子樹的最大深度可以通過調(diào)用本函數(shù)確定暑脆。
具體這樣實(shí)現(xiàn)：
class Solution:
"""
遞歸法
"""
def maxDepth(self, root):
def max_depth(root): # 計(jì)算以root為根節(jié)點(diǎn)的二叉樹的最大深度
if not root:
return 0
max_left = max_depth(root.left) # 左子樹最大深度
max_right = max_depth(root.right) # 右子樹最大深度
return max(max_left, max_right) + 1 # 加上根節(jié)點(diǎn)渠啤，返回當(dāng)前子樹最大深度
return max_depth(root)
方案2：迭代法
我們把每一個(gè)結(jié)點(diǎn)及其對應(yīng)的深度作為一條記錄，使用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)來存儲每條記錄添吗，遍歷樹的每一個(gè)結(jié)點(diǎn)沥曹，并用max_depth變量記錄遍歷到當(dāng)前位置的最大深度，直到棧中為空為止碟联。
class Solution:
"""
迭代法
"""
def maxDepth(self, root):
stack = [] # 定義一個(gè)空棧妓美，棧中的元素是結(jié)點(diǎn)及其對應(yīng)的深度
if root: # 如果根結(jié)點(diǎn)不為空
stack.append((root, 1)) # 則將根節(jié)點(diǎn)及其對應(yīng)深度1組成的元組入棧
max_depth = 0 # 初始化最大深度為零
while stack: # 當(dāng)棧非空時(shí)
tree_node, cur_depth = stack.pop() # 彈出棧頂結(jié)點(diǎn)及其對應(yīng)的深度
if tree_node: # 如果該結(jié)點(diǎn)不為空
max_depth = max(max_depth, cur_depth) # 更新當(dāng)前最大深度，如果該結(jié)點(diǎn)深度更大的話
stack.append((tree_node.left, cur_depth+1)) # 將該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)及其對應(yīng)深度壓入棧中
stack.append((tree_node.right, cur_depth+1)) # 將該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)及其對應(yīng)深度壓入棧中
return max_depth # 返回遍歷結(jié)束后的最大深度
如有疑問或建議鲤孵，歡迎評論區(qū)留言~
