Binary Tree Maximum Path Sum

Description

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]
   <strong>1</strong>
  <strong>/ \</strong>
 <strong>2</strong>   <strong>3</strong>

Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]
   -10
   / 

  9  20
    /  </strong>
   15   7

Output: 42

Solution(javascript)

const maxPathSum = (root) => {
  let max = -Infinity
  const aux = (node) => {
    if (!node) {
      return 0
    }
    const leftValue = aux(node.left)
    const rightValue = aux(node.right)
    max = Math.max(
      node.val + (leftValue <= 0 ? 0 : leftValue) + (rightValue <= 0 ? 0 : rightValue),
      max,
    )
    return (Math.max(leftValue, rightValue) <= 0 ? 0 : Math.max(leftValue, rightValue)) + node.val
  }
  aux(root)
  return max
}