124.二叉树中的最大路径和

链接：124.二叉树中的最大路径和
难度：Hard
标签：树、深度优先搜索、动态规划、二叉树
简介：给定一个非空二叉树，返回其最大路径和。

题解 1 - typescript

• 编辑时间：2020-06-21
• 执行用时：88ms
• 内存消耗：46.4MB
• 编程语言：typescript
• 解法介绍：递归调用判断部分和与单链和。

/**
 * 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 {
  const [link, part] = sum(root);
  return Math.max(link, part);
  function sum(node: TreeNode | null): [number, number] {
    if (node === null) return [0, -Infinity];
    const [linkSumL, partSumL] = sum(node.left);
    const [linkSumR, partSumR] = sum(node.right);
    const partSum = Math.max(
      node.val,
      node.val + linkSumL + linkSumR,
      node.val + linkSumL,
      node.val + linkSumR,
      partSumL,
      partSumR
    );
    const linkSum = Math.max(linkSumL, linkSumR, 0) + node.val;
    return [linkSum, partSum];
  }
}