Simple python solution

  • 0

    class Solution(object):
    def maxPathSum(self, root):
    return max(self._maxPathSum(root))

    def _maxPathSum(self, root):
        val = connected = disconnected = sum = root.val
        for node in [root.left, root.right]:
            if node is None: continue
            connected_ret, disconnected_ret = self._maxPathSum(node)
            connected    = max(connected_ret+val, connected)
            disconnected = max(disconnected_ret,  disconnected, connected_ret+val)
            sum += connected_ret
        return connected, max(sum, disconnected)

Log in to reply

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