Python recursive, piggyback on the height function.


  • 0
    J

    Take the fact that diameter is the longest among all longest paths passing each node and the fact:
    longest path passing though the current node = height (left child) + height(right child) + 2
    Need only one traversal of the tree. Update the max during the calculation of heights.

    class Solution(object):
        def diameterOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            self.dia = 0
            self.height(root)
            return self.dia
    
        def height(self, root):
            if not root: return -1
            l = self.height(root.left)
            r = self.height(root.right)
            self.dia = max(self.dia, l + r + 2)
            return max(l, r) + 1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.