二叉树中的最大路径和

题目描述

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 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

思路&js代码

1、递归

dfs 返回的是链的节点值之和

var maxPathSum = function(root) {
    let ans = -Infinity;
    // dfs 返回的是链的节点值之和
    function dfs(node) {
        if (node === null) {
            return 0; // 没有节点，和为 0
        }
        const lVal = dfs(node.left); // 左子树最大链和
        const rVal = dfs(node.right); // 右子树最大链和
        ans = Math.max(ans, lVal + rVal + node.val); // 两条链拼成路径
        return Math.max(Math.max(lVal, rVal) + node.val, 0); // 当前子树最大链和（注意这里和 0 取最大值了）
    }
    dfs(root);
    return ans;
};