树-二叉树的最大路径和

一、问题描述

二、解题思路

因为各个节点的值可能为负数，初始化res(最大路径和)的值为最小整数：Integer.MIN_VALUE

我们这里使用深度遍历（递归）的方法，先看某一个子树的情况：

这里有一个技巧，如果左、右子树贡献的值小于0时，可以将这个值设置为0，等价于舍弃该子树。

此时最大值为：res=Math.max(res,rootVal+leftVal+rightVal)

这里的rootVal+leftVal+rightVal包含多种情况（在递归过程中在下面值内保持最大值，这里好好理解一下，很巧妙的感觉）：

只有左子树：根节点和右子树一起贡献负值
左子树+根节点：此时右子树贡献负值：橘黄色箭头标识路径
只有根节点：左右子树均贡献负值
根节点+右子树：此时左子树贡献负值：蓝色箭头标识路径
只有右子树：左子树和根节点一起贡献负值
左子树+根节点+右子树贡献的值：红色箭头标识路径

三、代码实现

import java.util.*;/** public class TreeNode {*   int val = 0;*   TreeNode left = null;*   TreeNode right = null;*   public TreeNode(int val) {*     this.val = val;*   }* }*/public class Solution {int res=Integer.MIN_VALUE;/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @return int整型*/public int maxPathSum (TreeNode root) {if(root==null){return 0;}// 使用dfs记录路径和并返回resdfs(root);return res;}//从根节点深度遍历，public int dfs(TreeNode root){if(root==null){return 0;}int leftchildVal=Math.max(dfs(root.left),0);int rightchildVal=Math.max(dfs(root.right),0);int maxval=leftchildVal>rightchildVal?leftchildVal:rightchildVal;res=Math.max(res,root.val+leftchildVal+rightchildVal);return root.val+maxval;}
}