Binary Tree Maximum Path Sum

 //the design of this code is smart, from codeganker

这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目 中所说的可以起始和终结于任何结点。在这里树没有被看成有向图，而是被当成无向图来寻找路径。因为这个路径的灵活性，我们需要对递归返回值进行一些调整， 而不是通常的返回要求的结果。在这里，函数的返回值定义为以自己为根的一条从根到子结点的最长路径（这里路径就不是当成无向图了，必须往单方向走）。这个 返回值是为了提供给它的父结点计算自身的最长路径用，而结点自身的最长路径（也就是可以从左到右那种）则只需计算然后更新即可。这样一来，一个结点自身的 最长路径就是它的左子树返回值（如果大于0的话），加上右子树的返回值（如果大于0的话），再加上自己的值。而返回值则是自己的值加上左子树返回值，右子 树返回值或者0（注意这里是“或者”，而不是“加上”，因为返回值只取一支的路径和）。在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更 新。算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。

树的题目大多是用递归方式，但是根据要求的量还是比较灵活多变的，这道题是比较有难度的，他要用返回值去维护一个中间量，而结果值则通过参数来维护，需要一点技巧。 

class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int res = INT_MIN;
        maxPathSumRe(root, res);
        return res;
    }


//辅助函数的返回值定义为以自己为根的一条从根到子结点的最长值路径

    int maxPathSumRe(TreeNode *node, int &res)
    {
        if (!node) return 0;
        int l = maxPathSumRe(node->left, res);
        int r = maxPathSumRe(node->right, res);
        int sum =node->val+(l>0?l:0)+(r>0?r:0);
        res = max(res, sum);
        return node->val+max(l,max(r,0));
    }
};

//another flavor
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        int down=0;
        return maxPathSumRe(root, down);
    }
//down定义为以自己为根的一条从根到子结点的最长值路径
    int maxPathSumRe(TreeNode *node, int &down)
    {
        if(!node){
            down=0;
            return INT_MIN;
        }
        int ld,rd;
        int ls=maxPathSumRe(node->left,ld);
        int rs=maxPathSumRe(node->right,rd);
        down=node->val+max(0,max(ld,rd));
        return max(node->val+max(ld,0)+max(rd,0),max(ls,rs));
    }
};