力扣刷题：二叉树中的最大路径和

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

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

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

解析：
这道题使用递归来解题，重点是递归逻辑的设计以及返回值：
在当前节点（需要拐弯的那个节点）的路径和 = 左子树的最长路径和 + 右子树的最长路径和 + 当前节点的值
返回给父节点的是：
以当前节点为根节点的子树的最长路径和 + 当前节点的值
注意：
如果子树的和是负数，我们宁愿不选择这个子树，比如一个节点值是-10，左子树贡献-5，右子树贡献-3，最好的选择是都不要，返回0

具体代码：

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number} */varmaxPathSum=function(root){// 全局变量，用于记录整个树中的最大路径和// 初始化为负无穷，确保第一次比较时能被任何节点值更新letans=-Infinity/** * 深度优先搜索函数，递归计算每个节点的贡献值 * @param {TreeNode} node - 当前处理的节点 * @return {number} - 返回当前节点能向上贡献的最大路径和 */functiondfs(node){// 递归终止条件：空节点贡献值为0if(node===null){return0}// 递归计算左子树的最大贡献值// left表示：以node.left为起点的最大单向路径和constleft=dfs(node.left)// 递归计算右子树的最大贡献值// right表示：以node.right为起点的最大单向路径和constright=dfs(node.right)// 关键更新：以当前node为根节点的最大路径和// 这种情况考虑以node作为"转折点"的完整路径：// 可以包含左子树 + 当前节点 + 右子树// 这种情况不能向上传递给父节点，所以只用于更新全局答案ans=Math.max(ans,left+right+node.val)// 关键返回：当前节点能向上贡献的最大路径和// 这个返回值会被父节点使用，所以只能选择一边：// 1. Math.max(left, right) + node.val：选择左或右子树中更大的那个，加上当前节点// 2. 与0比较：如果贡献值是负数，就不选择这个子树（贡献0）// 这个返回值表示：从当前节点向上的单边最大路径和returnMath.max(Math.max(left,right)+node.val,0)}// 从根节点开始深度优先搜索dfs(root)// 返回整个树中的最大路径和returnans}