Given a binary tree, find the maximum path sum. （Hard）

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   3

 

Return 6.

 

分析：

问题是从树种任意点到任意点的最大path sum，且至少有一个点在路径上。

先考虑一个简单的问题，从顶点到任意点的最短路径（可以不包含任何点，即为0）

这样可以用一个简单的递归实现：

int singleSum(TreeNode* root) {        if (root == nullptr) {            return 0;        }        return max(0,root -> val + max(singleSum(root -> left), singleSum(root -> right)));}

再考虑pathSum与singleSum的关系；

pathSum采用分治的思想，可以求左子树的pathSum和右子树的pathSum，最后剩下的部分就是跨越根节点的pathSum

实际上也就是root->val加上左右子树的singlePath之和（如果小于0就不要了）。

程序：

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11     int singleSum(TreeNode* root) {12         if (root == nullptr) {13             return 0;14         }15         return max(0,root -> val + max(singleSum(root -> left), singleSum(root -> right)));16     }17 public:18     int maxPathSum(TreeNode* root) {19         if (root == nullptr) {20             return -0x7FFFFFFF;21         }22         int leftSum = maxPathSum(root -> left);23         int rightSum = maxPathSum(root -> right);24         int midSum = root -> val + max(0, (singleSum(root -> left) + singleSum(root -> right)));25         return max(midSum,max(leftSum, rightSum));26     }27 };

 

但是一组大样例居然超时了，考虑一下重复计算确实不少，给singleSum加一个hash表即可。

代码：

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11     unordered_map
     
       hash;12     int singleSum(TreeNode* root) {13         if (root == nullptr) {14             return 0;15         }16         if (hash.find(root) != hash.end()) {17             return hash[root];18         }19         int result = max(0,root -> val + max(singleSum(root -> left), singleSum(root -> right)));20         hash[root] = result;21         return result;22     }23 public:24     int maxPathSum(TreeNode* root) {25         if (root == nullptr) {26             return -0x7FFFFFFF;27         }28         int leftSum = maxPathSum(root -> left);29         int rightSum = maxPathSum(root -> right);30         int midSum = root -> val + max(0, (singleSum(root -> left) + singleSum(root -> right)));31         return max(midSum,max(leftSum, rightSum));32     }33 };