ConstDefinition 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) } }
/**
* 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)
* }
* }
*/
function maxPathSum(root: TreeNode | null): number {
let ans = -Infinity;
function dfs(node: TreeNode | null): number {
if (!node) {
return 0;
}
const l = dfs(node.left);
const r = dfs(node.right);
ans = Math.max(ans, l + r + node.val);
return Math.max(Math.max(l, r) + node.val, 0);
}
dfs(root);
return ans;
};
124.二叉树中的最大路径和
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点
root，返回其 最大路径和 。示例 1：
输入：
root = [1,2,3]输出：
6解释： 路径为 [2,1,3] ，2 + 1 + 3 = 6示例 2：
输入：
root = [-10,9,20,null,null,15,7]输出：
42解释： 路径为 [15,20,7] ，15 + 20 + 7 = 42提示：
[1, 3 * 10^4]-1000 <= Node.val <= 1000