Golang solution (39ms)


  • 0
    • Maintain a global maxSum to keep track of the maximum path sum seen so far.
    • At every node we need to compare the maximum of four values:
      (1) The node itself
      (2) The node + maximum path sum of the left subtree
      (3) The node + maximum path sum of the right subtree
      (4) The node + maximum path sum of both the left and right subtrees
    • We compute the max of #1, #2, #3 and assign it to maxSumEndingAtNode
    • Then we update the global maxSum with the maximum of either #4 or maxSumEndingAtNode.
    • Finally, we return maxSumEndingAtNode, since this value represents the maximum path sum of the subtree rooted at this node.
    func maxPathSum(root *TreeNode) int {
        maxSum := math.MinInt32
        maxPathSumHelper(root, &maxSum)
        return maxSum
    }
    
    func maxPathSumHelper(node *TreeNode, maxSum *int) int {
        if node == nil { return 0 }
        left, right := maxPathSumHelper(node.Left, maxSum), maxPathSumHelper(node.Right, maxSum)
        maxSumEndingAtNode := max(node.Val, node.Val + max(left, right))
        *maxSum = max(*maxSum, max(node.Val + left + right, maxSumEndingAtNode))
        return maxSumEndingAtNode
    }
    
    func max(x, y int) int { if x > y { return x }; return y }
    

Log in to reply
 

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