题目链接：https://leetcode.com/problems/binary-tree-maximum-path-sum/
题中要求 maxPathSum(TreeNode *root) 函数返回二叉树中最大的 "Path Sum"。
而这个最大的 "Path Sum" 可以被分解为三部分之和：
"左子树的根节点" 到 "左子树的某个节点" 的 最大 "Path Sum"。
"右子树的根节点" 到 "右子树的某个节点" 的 最大 "Path Sum"。
根节点的值。
当第1/2部分所求的 "Path Sum" 为负值时，我们求和的时候不加入它(们)。
对二叉树中的每个节点都计算这3部分之和，最大的和就是题目所要求的值。
Leetcode #124 Binary Tree Maximum Path Sum
原文：http://www.cnblogs.com/meowcherry/p/4394880.html