给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
输出: 42
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
解题思路：
- 首先想到用递归实现DFS遍历所有的点
- 更新当前节点，节点值表示此节点为根节点的子树如果被上级路径连接，它能贡献的最大路径和 ：
rootValue = Math.max(rootValue, rootValue+leftValue, rootValue+rightValue);
这里不能加rootValue+leftValue+rightValue是因为路径不能走回头路！！！
-更新结果：
result = Math.max(leftValue, rightValue, result, rootValue, leftValue + rightValue + rootValue);
public class MaxPathSum {
static int result = -0x3f3f3f3f;
public int maxPathSum(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return root.val;
result = -0x3f3f3f3f;
dfs(root);
return result;
}
private int dfs(TreeNode root) {
if (root.left == null && root.right == null) return root.val;
int leftValue = 0;
int rightValue = 0;
if (root.left != null) {
leftValue = dfs(root.left);
result = Math.max(leftValue, result);
}
if (root.right != null) {
rightValue = dfs(root.right);
result = Math.max(rightValue, result);
}
//定义sum是因为路径不能重复，因此如果当前点要是想和上一级点连接，就只能取leftValue + root.val 或者rightValue + root.val或者root.val
int sum = rightValue + root.val + leftValue;
root.val = Math.max(Math.max(rightValue + root.val, root.val), leftValue + root.val);
result = Math.max(result,sum);
return root.val;
}
public static void main(String[] args) {
}
}
