Python recursive, piggyback on the height function.

  • 0

    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
            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.