问题描述：
给定一个二叉树的头节点head，路径的规定有以下三种不同的规定：
- 路径必须是头节点出发，到叶节点结束，返回最大路径和
- 路径可以从任意节点出发，但必须往下走到达任何节点，返回最大路径和
- 路径可以从任意节点出发，到任何节点，返回最大路径和
- 路径可以从任意节点出发，到叶节点结束，返回最大路径和
思路
定义Node节点
public static class Node {
public int value;
public Node left;
public Node right;
public Node(int val) {
value = val;
}
}规定一（路径必须是头节点出发，到叶节点结束，返回最大路径和）思路：
最大路径和 = 每条路径走到叶节点的最大路径和，所以每次往下走，走到叶节点，和之前最大的路径和比较。
路径和 = 当前的节点 + 之前的路径和。
public static int maxSum = Integer.MIN_VALUE;
public static int maxPath(Node head) {
maxSum = Integer.MIN_VALUE;
p(head, 0);
return maxSum;
}
public static void p(Node x, int pre) {
if (x.left == null && x.right == null) {
maxSum = Math.max(maxSum, pre + x.value);
}
if (x.left != null) {
p(x.left, pre + x.value);
}
if (x.right != null) {
p(x.right, pre + x.value);
}
}另外一种思路是按照二叉树的递归套路： x为头的整棵树上，最大路径和是多少，返回。路径要求：一定从x出发，到叶节点，算一个路径。
public static int maxDis(Node head) {
if (head == null) {
return 0;
}
return process2(head);
}
public static int process2(Node x){
if (x.left ==null&& x.right==null){
return x.value;
}
int next = Integer.MIN_VALUE;
if (x.left !=null){
next = process2(x.left);
}
if (x.right!=null){
next = Math.max(next,process2(x.right));
}
return x.value+next;
}
规定二（路径可以从任意节点出发，但必须往下走到达任何节点，返回最大路径和）思路：
从任意节点出发且只能往下，所以有可能与头节点有关，有可能与头节点无关。所以可以分为两大类五种情况。
第一类：与头节点x无关
1.自己左子树上的整体最大路径和 2.自己右子树上的整体最大路径和
第二类：与头节点x有关
3. 只有自己一个节点 4.x往左走 5.x往右走
public static int maxSum2(Node head) {
if (head == null) {
return 0;
}
return f(head).allTreeMaxSum;
}
public static class Info {
public int allTreeMaxSum;
public int fromHeadMaxSum;
public Info(int all, int from) {
allTreeMaxSum = all;
fromHeadMaxSum = from;
}
}
public static Info f(Node x) {
if (x == null) {
return null;
}
Info leftInfo = f(x.left);
Info rightInfo = f(x.right);
//X无关时，左树上的整体最大路径和
int p1 = Integer.MIN_VALUE;
if (leftInfo != null) {
p1 = leftInfo.allTreeMaxSum;
}
//X无关时，右树上的整体最大路径和
int p2 = Integer.MIN_VALUE;
if (rightInfo != null) {
p2 = rightInfo.allTreeMaxSum;
}
//X有关，x自己
int p3 = x.value;
//x有关 x往左走
int p4 = Integer.MIN_VALUE;
if (leftInfo != null) {
p4 = x.value + leftInfo.fromHeadMaxSum;
}
//x有关 x往右走
int p5 = Integer.MIN_VALUE;
if (rightInfo != null) {
p5 = x.value + rightInfo.fromHeadMaxSum;
}
int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));
int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
return new Info(allTreeMaxSum, fromHeadMaxSum);
}规定三（路径可以从任意节点出发，到任何节点，返回最大路径和）思路：
从任意节点到任意节点，所以在问题2的基础上只需要再加一种可能性，即与头节点有关时，最大路径和是x既往左走，又往右走。
第一类：与头节点x无关
1.自己左子树上的整体最大路径和 2.自己右子树上的整体最大路径和
第二类：与头节点x有关
3. 只有自己一个节点 4.x往左走 5.x往右走 6.x既往左走又往右走
public static int maxSum3(Node head) {
if (head == null) {
return 0;
}
return f2(head).allTreeMaxSum;
}
public static Info f2(Node x) {
if (x == null) {
return null;
}
Info leftInfo = f2(x.left);
Info rightInfo = f2(x.right);
//X无关时，左树上的整体最大路径和
int p1 = Integer.MIN_VALUE;
if (leftInfo != null) {
p1 = leftInfo.allTreeMaxSum;
}
//X无关时，右树上的整体最大路径和
int p2 = Integer.MIN_VALUE;
if (rightInfo != null) {
p2 = rightInfo.allTreeMaxSum;
}
//X有关，x自己
int p3 = x.value;
//x有关 x往左走
int p4 = Integer.MIN_VALUE;
if (leftInfo != null) {
p4 = x.value + leftInfo.fromHeadMaxSum;
}
//x有关 x往右走
int p5 = Integer.MIN_VALUE;
if (rightInfo != null) {
p5 = x.value + rightInfo.fromHeadMaxSum;
}
//x有关 x既往左走又往右走
int p6 = Integer.MIN_VALUE;
if (leftInfo!=null && rightInfo!=null){
p6 = x.value + leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum;
}
int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(Math.max(p4,p5), p6));
int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
return new Info(allTreeMaxSum, fromHeadMaxSum);
}规定四（路径可以从任意节点出发，到叶节点结束，返回最大路径和 ）思路：
首先设定一个全局变量max，然后遍历每一个节点到叶节点的路径，然后与max最更新。
public static int max = Integer.MIN_VALUE;
public static int f3(Node head) {
if (head.left == null && head.right == null) {
max = Math.max(max, head.value);
return head.value;
}
int nextMax = 0;
if (head.left != null) {
nextMax = f3(head.left);
}
if (head.right != null) {
nextMax = Math.max(nextMax, f3(head.right));
}
int ans = head.value + nextMax;
max = Math.max(max, ans);
return ans;
}