code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

124 Binary Tree Maximum Path Sum

/**
 *
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}

const binaryTreeMaximumPathSum = root => {
  if (!root) {
    return 0
  }
  if (!root.left && !root.right) {
    return root.val
  }
  let maxSum = -Infinity
  const traverse = root => {
    if (!root.left && !root.right) {
      maxSum = Math.max(root.val, maxSum)
      return root.val
    }
    let left = 0
    let right = 0
    if (root.left) {
      left = Math.max(traverse(root.left), 0)
    }
    if (root.right) {
      right = Math.max(traverse(root.right), 0)
    }
    maxSum = Math.max(left + right + root.val, maxSum)
    return Math.max(left + root.val, right + root.val, 0)
  }
  traverse(root)
  return maxSum
}

test('binaryTreeMaximumPathSum', () => {
  const t1 = new TreeNode(-2)
  t1.left = new TreeNode(-1)
  expect(binaryTreeMaximumPathSum(t1)).toEqual(-1)
})

Created 2021-01-30T23:10:21+05:18, updated 2021-01-31T00:25:36+05:18 · History · Edit