Binary Tree Maximum Path Sum

1. Problem Description

A path is defined as a sequence of nodes starting from any node in the tree and following parent-child connections to any other node. The same node may appear at most once in a path. A path contains at least one node and does not necessarily pass through the root.

The path sum is the sum of the node values in the path.

Given the root root of a binary tree, return its maximum path sum.

2. Approach

• DFS

3. Implementation

3.1. DFS

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt64
    dfs(root, &maxSum)
    return maxSum
}

func dfs(root *TreeNode, maxSum *int) int {
    if root == nil {
        return 0
    }

    // Compute the maximum contribution from the left subtree; if it is negative, use 0 instead
    leftMaxSum := max(0, dfs(root.Left, maxSum))
    // Compute the maximum contribution from the right subtree; if it is negative, use 0 instead
    rightMaxSum := max(0, dfs(root.Right, maxSum))
    *maxSum = max(*maxSum, root.Val + leftMaxSum + rightMaxSum)
    // Return the maximum one-sided path sum. We do not return *maxSum because *maxSum may include both subtrees; adding root again would no longer form a valid single path
    return root.Val + max(leftMaxSum, rightMaxSum)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

4. References

• Binary Tree Maximum Path Sum: Clear Recursive Solution - LeetCode