題目
難度：★★☆☆☆
類型：二叉樹
給定一棵二叉樹即寒，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結(jié)點路徑長度中的最大值召噩。這條路徑可能穿過根結(jié)點母赵。
注意：兩結(jié)點之間的路徑長度是以它們之間邊的數(shù)目表示。
示例
給定二叉樹
1
/ \
2 3
/ \
4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]具滴。
解答
class Solution:
def diameterOfBinaryTree(self, root) -> int:
if not root:
return 0
res = []
self.dfs(root, res)
return max(res) - 1
def dfs(self, root, res):
if not root:
return 0
left = self.dfs(root.left, res)
right = self.dfs(root.right, res)
res.append(left + right + 1)
return max(left, right) + 1
如有疑問或建議凹嘲，歡迎評論區(qū)留言~
