For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example: Given the below binary tree,
1 / \ 2 3Return 6.
题目的大意是给定一棵二叉树，求二叉树中的一条路径，使得路径上所以点对应的值相加得到的和最大，并返回最大的和，我们把这个和称为路径和。
解决这道题使用的是类似深度优先搜索的算法，需要注意的是，这道题目中结点的值有可能是负数，所以算法会复杂一些。
我们用一个全局变量maxlen来记录当前得到的最大和，每遍历一个节点时，先递归地调用函数，分别求以左、右儿子结点为起点到他们的叶子结点的所有路径和的最大值（这里的所有路径包括没有到达叶子结点的路径）。
然后求在这个结点为根结点的子树中，该结点是路径中一点的所以路径的最大路径和，如果这个最大路径和比当前的最大路径和大，就更新当前的最大路径和。这时候最大的路径和所代表的路径有4种情况：
（1）只有这一个结点的路径。
（2）路径包含了这个结点和它左边子树部分结点。
（3）路径包含了这个结点和它右边子树部分结点。
（4）路径包含了这个结点以为，还同时包含了它左边和右边子树的部分结点。
分别对这4中情况进行判断，更新当前的最大路径和。
当把所有节点都遍历了以后，当前的最大路径和就是整棵数的最大路径和。
因为使用的是深度优先搜索算法，图又是一棵二叉树，所有时间复杂度是O(n)。以下为源代码：
class Solution { public: int maxlen=-10000000; int maxPathSum(TreeNode* root) { int t=dfs(root); return maxlen; } int dfs(TreeNode* r) { if(r==NULL) return 0; int leftlen=dfs(r->left); int rightlen=dfs(r->right); if(leftlen+rightlen+r->val>maxlen) maxlen=leftlen+rightlen+r->val; if(r->val+leftlen>maxlen) maxlen=r->val+leftlen; if(r->val+rightlen>maxlen) maxlen=r->val+rightlen; if(r->val>maxlen) maxlen=r->val; int t=max(leftlen,rightlen); return r->val+max(t,0); } };