题目
难度：★★☆☆☆
类型：二叉树
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
注意：两结点之间的路径长度是以它们之间边的数目表示。
示例
给定二叉树
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
如有疑问或建议，欢迎评论区留言~
