Maximum path sum in a tree
Hardtreedfsdynamic programmingrecursion
A path is a sequence of nodes where each adjacent pair is connected by an edge and no node repeats. It needn't pass through the root and has at least one node. Return the largest sum of values along any path.
Examples write a tree level by level, with null for a missing child: [3,9,20,null,null,15,7].
Example 1
Input: root = [1,2,3] Output: 6
2 → 1 → 3 = 6.
Example 2
Input: root = [-10,9,20,null,null,15,7] Output: 42
15 → 20 → 7 = 42.
Constraints
- 1 ≤ number of nodes ≤ 3·10⁴
- -1000 ≤ Node.val ≤ 1000
Submit checks your solution against 9 tests, including hidden ones.
// Provided by the judge: keep these definitions
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val
this.left = left
this.right = right
}
}
/**
* @param {TreeNode|null} root
* @return {int}
*/
function maxPathSum(root) {
}