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)