Simple Python

  • 0

    For each node keep track of 2 things:

    1. local max including node itself
    2. max between left and right subtree

    #2 will keep track of the longest path with the node as part of the sequence while #1 keep track of the longest path curving around the node.

    class Solution(object):
        def helper(self, node):
            if not node: return 0, 0
            left, lMax = self.helper(node.left)
            right, rMax = self.helper(node.right)
            return max(left, right)+1, max(lMax, rMax, left+right)
        def diameterOfBinaryTree(self, root):
            :type root: TreeNode
            :rtype: int
            return self.helper(root)[1]

Log in to reply

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