給定一個(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 说贝。
- show the code:
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
l_height = self.maxDepth(root.left)
r_height = self.maxDepth(root.right)
return max(l_height,r_height)+1
- 此題屬于二叉樹的經(jīng)典題也是入門題,看到題目可以聯(lián)想到遞歸慎颗,求二叉樹的最大深度乡恕,可以轉(zhuǎn)化為求其左右子樹深度的較大者然后加一,依次往下俯萎。
- 注意遞歸的出口為遍歷到葉子節(jié)點(diǎn)傲宜,返回值為0,因?yàn)檫@里我們需要的返回值是一個(gè)數(shù)值夫啊。