Time: 2019-08-11
題目描述
給定一個(gè)二叉樹油猫，找出其最大深度隆夯。
二叉樹的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)噪沙。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)插爹。
示例：
給定二叉樹 [3,9,20,null,null,15,7]哄辣，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 请梢。
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)力穗，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處毅弧。
思路
深度遍歷二叉樹，遍歷過(guò)程中記錄深度值当窗，在葉子結(jié)點(diǎn)處比較够坐，更新當(dāng)前最大深度。
代碼
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
self.maxDepth = 0
self.dfs(root, 0)
return self.maxDepth
def dfs(self, root, depth):
if root == None:
if self.maxDepth < depth:
self.maxDepth = depth
return
self.dfs(root.left, depth + 1)
self.dfs(root.right, depth + 1)
時(shí)空復(fù)雜度
時(shí)間復(fù)雜度：O(n)
END.
