企业官网建设流程全解析

题目

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

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

给你一个二叉树的根节点 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进行贡献，因此当前最大值是10+5）

10/\-205

• 由此可以计算最优路径为 Max（之前的max，左侧最大+root.val+右侧最大）
• 向上递归时，传递的不是计算得到的最优路径，而是Max（左边路径+根节点，右边路径+根节点）

staticintmax;publicstaticintmaxPathSum(TreeNoderoot){//如果同一个程序里调用 maxPathSum() 多次，前一次计算出来的 max 可能影响下一次max=Integer.MIN_VALUE;dfs(root);returnmax;}privatestaticintdfs(TreeNoderoot){if(root==null)return0;intleftmax=Math.max(0,dfs(root.left));intrightmax=Math.max(0,dfs(root.right));max=Math.max(max,root.val+leftmax+rightmax);returnMath.max(root.val+leftmax,root.val+rightmax);}