题目二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 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提示树中节点数目范围是 [1, 3 * 10^4]-1000 Node.val 1000解题思路考虑最优路径经过当前处理的root节点的各种情况计算左子树向上传递到达root节点的最大值计算右子树向上传递到达root节点的最大值左右子树可能存在负贡献的情况如下例子所示左子树给10 的贡献是负数所以和0进行比较此时的0代表不进行贡献。右子树给10进行贡献因此当前最大值是10510/\-205由此可以计算最优路径为 Max之前的max左侧最大root.val右侧最大向上递归时传递的不是计算得到的最优路径而是Max左边路径根节点右边路径根节点staticintmax;publicstaticintmaxPathSum(TreeNoderoot){//如果同一个程序里调用 maxPathSum() 多次前一次计算出来的 max 可能影响下一次maxInteger.MIN_VALUE;dfs(root);returnmax;}privatestaticintdfs(TreeNoderoot){if(rootnull)return0;intleftmaxMath.max(0,dfs(root.left));intrightmaxMath.max(0,dfs(root.right));maxMath.max(max,root.valleftmaxrightmax);returnMath.max(root.valleftmax,root.valrightmax);}