题目：
Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ 2 3
Return 6.
节点可能为负数，寻找一条最路径使得所经过节点和最大。路径可以开始和结束于任何节点但是不能走回头路。
这道题虽然看起来不同寻常，但是解法仍然不外乎二叉树的遍历。
我们先拿根节点讨论，对于根节点，最终那条最长的路径要么经过它，要么不经过。我们只要在两种情况下的路径中选出最长的就可以了。
(1)如果不经过，那么最长路径要么全在左子树，要么全在右子树
(2)如果经过，那么我们只要找出左子树中到达根节点的最大路径长度a，和右子树中到达根节点的最大路径长度b。然后找出MAX(a+b+node.val, a+node.val, b+node.val, node.val)
将(1) (2) 综合考虑，选出最大值即可。
如果我们定义一个函数，它的参数是一个节点，它的返回值是一条路径的最大长度，但是这个路径必须有一个头是输入的节点。
那么函数func(node)的return值可以这样定义：return MAX(func(node.left)+node.val, func(node.right)+node.val, node.val)
这样对于当前节点，调用函数处理其子节点，返回的路径长度都是能接到当前节点上去的。
同时，我们不能忘了判断当前子树中的最大长度是多少，判断方式如上面(1) (2) 所述，需要考虑不经过当前节点的情况。将最大值存入全局变量MAX
终止条件是node == null，直接返回0。
这样如果我们调用func(root)，完成后MAX中存的值就是所求结果。
时间复杂度 O(n)，n为总节点数
代码：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxPathSum(TreeNode *root) { maxPathSumCore(root); return MAX; } int maxPathSumCore(TreeNode *node) { if(NULL == node) return 0; int a = maxPathSumCore(node -> left); int b = maxPathSumCore(node -> right); if((a+b+node->val) > MAX) MAX = (a+b+node->val); if((a+node->val) > MAX) MAX = (a+node->val); if((b+node->val) > MAX) MAX = (b+node->val); if(b > MAX && node -> right != NULL) MAX = b; if(a > MAX && node -> left != NULL) MAX = a; if(node->val > MAX) MAX = node->val; int maxViaThisNode = ((a + node->val) > node->val ? (a + node->val) : node->val); return (maxViaThisNode > (b + node->val) ? maxViaThisNode : (b + node->val)); } private: int MAX= -99999999; };
[LeetCode] 二叉树里的最长路径,布布扣,bubuko.com
原文：http://www.cnblogs.com/felixfang/p/3637984.html