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

二叉树中的最大路径和

力扣原题

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 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

/*** 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}*/
var maxPathSum = function(root) {let max = -Number.MAX_VALUE // 递归过程更新最大值function dfs(node) {if(!node) return 0const val = node.valconst leftMax = dfs(node.left)const rightMax = dfs(node.right)// 1. 当前节点最大贡献值 = 当前节点值 + 左子树最大贡献值 + 右子树最大贡献值const sum = val + Math.max(leftMax, 0) + Math.max(rightMax, 0) max = Math.max(max, sum) // 更新最大值if(!node.left && !node.right) {// 2.1. 叶子节点：非负数时作为最大贡献值返回，否则最大贡献值为0return Math.max(val, 0)} else {// 2.2 非叶子节点:  当前节点值 + 取其中的最大值（左子树最大贡献值,右子树最大贡献值）const childMax = Math.max(leftMax, rightMax)return Math.max(val + childMax, 0) // 大于0才选为最大贡献值递归，否则不选相当于0}}dfs(root)return max
};

解题思路

核心思路，把所有节点，都当作只有当前根节点+左子树+右子树
获取节点最大贡献值，和递归的最大贡献值，逻辑不一样。
获取当前节点最大贡献值，相当于以当前节点作为根节点了，最大贡献值就是当前节点加左子树和右子树的最大贡献值
而当往回递归时，当前节点不作为根节点，而是子树，此时递归返回的最大贡献值，只能选择其一，否则就存在分叉了

1. 要获取当前节点的，最大路径和（以下称为最大贡献值），显而易见得到：
   当前节点最大贡献值 = 当前节点值 + 左子树最大贡献值（非负） + 右子树最大贡献值（非负）

2. 但是如何保证不出现分叉，那就需要在递归的时候进行限制了，递归条件：
   2.1 叶子节点：非负数时作为最大贡献值返回，否则最大贡献值为0
   2.2 非叶子节点: 当前节点值 + 取其中的最大值（左子树最大贡献值,右子树最大贡献值）