Function maxPathSumHelper

kotlin/Trees/MaximumPathSum.kt:21–36

}

fun maxPathSumHelper(node: TreeNode?, maxSum: MutableList<Int>): Int {
    // Base case: null nodes have no path sum.
    if (node == null) {
        return 0
    }
    // Collect the maximum gain we can attain from the left and right
    // subtrees, setting them to 0 if they're negative.
    val leftSum = Math.max(maxPathSumHelper(node.left, maxSum), 0)
    val rightSum = Math.max(maxPathSumHelper(node.right, maxSum), 0)
    // Update the overall maximum path sum if the current path sum is
    // larger.
    maxSum[0] = Math.max(maxSum[0], node.value + leftSum + rightSum)
    // Return the maximum sum of a single, continuous path with the
    // current node as an endpoint.
    return node.value + Math.max(leftSum, rightSum)
}