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

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

1. 递归。每次fun(root),更新全局max=Math.max(max，root.val+fun(root.left)+fun(root.right))，返回的是以root节点为根的最大贡献值return root.val+Math.max(fun(root.left)，fun(root.right))。返回不能是加上左右子树的总和，因为要保证每个节点只计算一次，只有在确定根后才能把左右子树的贡献合起来。