Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes in which each pair of neighbours is joined by an edge and no node appears twice. A path may start and end at any nodes: it does not have to pass through the root, and it can climb up to a node and come back down on the other side.
The path sum is the total of the values of the nodes on the path. Given the root of a non-empty binary tree, return the largest path sum over all non-empty paths.
Values can be negative. A single node on its own is a valid path.
Constraints
- The tree has between
1and3 * 10^4nodes. -1000 <= Node.val <= 1000
Examples
Example 1
Input: root = [-3,4,5,-1,6,null,-2] Output: 12
The best path is 6 → 4 → -3 → 5 = 12. It passes through the negative root because both sides are worth more than -3 costs.
Example 2
Input: root = [-7] Output: -7
A path needs at least one node, so a lone negative node is the answer.
Example 3
Input: root = [-10,5,-20,8,7] Output: 20
8 → 5 → 7 = 20. Going up to the root would only add -10, so the best path bends at 5.
JavaScript you'll use: Recursion, the call stack and memoization Functions, arrow functions and closures Numbers, Math and integer tricks
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
function maxPathSum(root) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.