0124-binary-tree-maximum-path-sum.ts

/**
 * Definition for a binary tree node.
 * class TreeNode {
 * val: number
 * left: TreeNode | null
 * right: TreeNode | null
 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 * }
 */

functionmaxPathSum(root: TreeNode|null): number{
constres=[root.val];

// return max path sum without split
functiondfs(root: TreeNode|null): number{
if(!root){
return0;
}

letleftMax=dfs(root.left);
letrightMax=dfs(root.right);
leftMax=Math.max(leftMax,0);
rightMax=Math.max(rightMax,0);

// compute max path sum WITH split
res[0]=Math.max(res[0],root.val+leftMax+rightMax);
returnroot.val+Math.max(leftMax,rightMax);
}

dfs(root);
returnres[0];
}