题目：
难度：Hard
相关话题：树、深度优先搜索
给定一个非空 二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个 节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
思路：
对于某一个节点root，它可以有2种选择：
可以看到，1和2内部存在重复，因此减少重复后，不与父节点连接的实际就是：
Math.max(左节点值+当前值+右节点值，左节点值，右节点值)
最终从1和2中选取出最大的值。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
let res=-Infinity
function _maxPathSum(root) {
if(!root)return -Infinity
let leftV=_maxPathSum(root.left),
rightV=_maxPathSum(root.right),
cV=root.val
// 与父节点连接中断的path的数值
res=Math.max(res,leftV,rightV,cV+leftV+rightV)
// 与父节点连接继续的path的数值
return Math.max(cV+leftV,cV+rightV,cV)
}
return Math.max(_maxPathSum(root),res)
};