MaxPathSum
最早和瞿神合作写了一个比较复杂的版本的，现在打算 重新写，虽然 都是树形DP。
因此，每次调用左右子树的时候，要特别注意是否有一个是树杈行，有O(n)的算法，每次做两件事情，分别是更新基于当前root的path的最大值，四种选最大。
max{f(x.l)+f(x.r)+w(x),f(x.l)+w(x),f(x.r)+w(x),w(x)};
每个节点是递归找两个子树的最大，但是除去两个子树都需要的情况，三种选较大的，不然递归返回回去不能作为 父亲的子问题
最大PathSum
class Solution {
public:
int maxPath;
int maxPathSum(TreeNode *root)
{
if(!root) return 0;
maxPath=root->val;
maxPathNode(root);
return maxPath;
}
int maxPathNode(TreeNode *root)
{
if(root==NULL) return 0;
int leftmax=maxPathNode(root->left), rightmax=maxPathNode(root->right);
maxPath=max(root->val, max(maxPath,max(leftmax+root->val+rightmax, max(leftmax+root->val, rightmax+root->val))));
//cout<<maxPath<<endl;
return max(root->val, max(leftmax+root->val, rightmax+root->val));
}
};
今天突然发现stack.top() 是返回引用类型，这样的好处是可以S.top()=a; 函数返回值可以作为左值进行赋值操作，后者说cout<<a类似这种可以连续操作