给定一个非空二叉树，返回其最大路径和。
路径 : 一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
用例
输入: [1,2,3]
1
/
2 3
输出: 6
输入: [-10,9,20,null,null,15,7]
-10
/
9 20
/
15 7
输出: 42
通过 &max 来记录全局最大值，通过返回ret来记录递归返回的值
二叉树 abc，a 是根结点（递归中的 root），bc 是左右子结点（代表其递归后的最优解）。
最大的路径，可能的只有三种路径情况：
a
/
b c
- b + a + c。
- b + a + a父
- a + c + a父
其中情况 1，表示如果不联络父结点的情况，或本身是根结点的情况。
这种情况是没法递归的，但是结果有可能是全局最大路径和。
情况 2 和 3，递归时计算 a+b 和 a+c，选择一个更优的方案返回，也就是上面说的递归后的最优解啦。
另外结点有可能是负值，最大和肯定就要想办法舍弃负值（max(0, x)）（max(0,x)）。
但是上面 3 种情况，无论哪种，a 作为联络点，都不能够舍弃。
暴力枚举法
int result = -2147483648;
int helper(struct TreeNode* root) {
if (root == NULL) return 0;
int left = helper(root->left);
int right = helper(root->right);
int threeNodeSum = root->val + left + right;
int twonodeSum = root->val + max(left, right);
int oneNodeSum = root->val;
int ret = max(twoNodeSum, oneNodeSum);
int currentMax = max(ret, threeNodeSum);
result = max(currentMax, result);
return ret;
}
int max(int a, int b) {
return a > b ? a : b;
}
int maxPathSum(struct TreeNode* root){
result = -2147483648;
int temp = helper(root);
return result;
}
#define max(a, b) ((a) > (b) ? (a) : (b))
int maxPath = INT_MIN;
int dfs(struct TreeNode *root) {
if (root == NULL) {
return 0;
}
// 左子树的最大和
int left = dfs(root->left);
// 右子树的最大和
int right = dfs(root->right);
// 当前节点路径(不需要联系父结点，或本身就已经是根结点而无父节点)的最大值 VS 当前全局最大值
maxPath = max(left + right + root->val, maxPath);
// 需要联系父节点，因此只返回子树最大分支
return max(0, max(left, right) + root->val);
}
int maxPathSum(struct TreeNode *root) {
// 初始化为最小可能的整数
maxPath = INT_MIN;
// 深度优先遍历
dfs(root);
return maxPath;
}
欢迎关注全是干货的:JavaEdge
