给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 2:
输入: [-10,9,20,null,null,15,7]
-10 / \ 9 20 / \ 15 7
输出: 42
思路：
每个节点都有两个状态：
1，到这里还得往上走，此时自然不可能会有从该节点左边到右边的路线（因为要往上走），记为该节点的x值。
2，到这里就不往上走了，记为该节点的y值。
每个节点的x值等于max（本节点的值，左子节点的x值，右子节点的x值）
每个节点的y值等于max（本节点的值，左子节点的y值，右子节点的y值， 本节点的值+左子节点的x值+右子节点的x值，本节点的值+左子节点的x值，本节点的值+右子节点的x值）PS:后面两个红色的是因为某些节点可能只有一个子节点 。
最后求根节点的max（x，y）即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int max_(int x, int y, int w){
int a = max(x, y);
return max(a, w);
}
int max_4(int x, int y, int w, int z, int a, int b){
int c = max(x, y);
int d = max(w, z);
int h = max(a, b);
return max_(c, d, h);
}
vector<int> treeDp(TreeNode* root){
vector<int>ans;
if(root->left || root->right){
vector<int>node={-9999999,-9999999};
vector<int>leftN = root->left?treeDp(root->left):node;
vector<int>rightN = root->right?treeDp(root->right):node;
int nonStop = root->val + max_(0, rightN.at(0), leftN.at(0));
int stop = max_4(root->val, leftN.at(1), rightN.at(1), leftN.at(0) + rightN.at(0) + root->val, root->val + leftN.at(0), root->val+rightN.at(0));
ans.push_back(nonStop);
ans.push_back(stop);
return ans;
}
ans.push_back(root->val);
ans.push_back(root->val);
return ans;
}
int maxPathSum(TreeNode* root) {
vector<int>ans = treeDp(root);
return max(ans.at(0), ans.at(1));
}
};
