image.png
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
height = {None:(0,0)}
def getheight(root):
if root in height: return height[root]
l,r = getheight(root.left), getheight(root.right)
res = (1+max(l), 1+max(r))
height[root] = res
return res
getheight(root)
def helper(root):
if not root: return 0
return max([helper(root.left), helper(root.right), sum(height[root])-2])
return helper(root)
