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 3Return
6.
题目意思很简单，就是给定一棵二叉树，求最大路径和。path 可以从任意 node 开始，到任意 node 结束。
这道题在 LeetCode 上的通过率只有 20% 多一点，并被标记为 Hard ，但实际上这是一道相当好的问题，在北美的 CS 求职面试中也是一道高频题，下文我将尝试用最容易理解的方式去分析这道题目。
我的思路
1. 我们直接从题目的问题来分析。给定一棵二叉树，我们怎么来求其最大路径和呢？稍做思考，不难得到以下结论：
当前二叉树的双路
最大路径和 = max(左子树的双路最大路径和, 右子树的双路最大路径和, 当前二叉树在包含根结点情况下的双路最大路径和);
2. 很显然，要解决上面的问题，关键在于怎么求二叉树在包含根结点情况下的双路最大路径和，而要求二叉树在包含根结点情况下的双路最大路径和，首先得先求二叉树的单路最大路径和，请看以下分析：
当前二叉树的单路
最大路径和 = max(左子树的单路最大路径和 + 根结点值, 右子树的单路最大路径和 + 根结点值, 根结点值);
当前二叉树在包含根结点情况下的双路
最大路径和 = 左子树的单路最大路径和 + 根结点值 + 右子树的单路最大路径和;
3. 通过 1 和 2，我们很容易发现，该题可以采用分治法来解决，实际上，与二叉树有关的绝大多数问题，我们都可以采用分治的思想。通常，分治法避免使用全局变量，因此我将会封装一个 returnType 类型，来作为返回值，如下：
struct returnType
{
returnType(const int maxSinglePathSum, const int maxDoublePathSum)
: maxSinglePathSum_(maxBranch), maxDoublePathSum_(maxSum)
{ } int maxSinglePathSum_;
int maxDoublePathSum_;
};
4. 可以 AC 的完整源代码如下：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/ struct returnType
{
returnType(const int maxSinglePathSum, const int maxDoublePathSum)
: maxSinglePathSum_(maxSinglePathSum), maxDoublePathSum_(maxDoublePathSum)
{ } int maxSinglePathSum_;
int maxDoublePathSum_;
}; class Solution
{
public:
int maxPathSum(TreeNode *root)
{
return maxPathRec(root).maxDoublePathSum_;
} returnType maxPathRec(TreeNode *root)
{
if (root == NULL)
{
return returnType(0, numeric_limits<int>::min());
} // Devide
returnType left = maxPathRec(root->left);
returnType right = maxPathRec(root->right); // Conquer
int subMaxSinglePathSum = max(left.maxSinglePathSum_, right.maxSinglePathSum_);
int maxSinglePathSum = root->val;
maxSinglePathSum = max(subMaxSinglePathSum + maxSinglePathSum, maxSinglePathSum); int subMaxDoublePathSum = max(left.maxDoublePathSum_, right.maxDoublePathSum_);
int maxDoublePathSum = max(maxSinglePathSum, left.maxSinglePathSum_ + root->val + right.maxSinglePathSum_);
maxDoublePathSum = max(subMaxDoublePathSum, maxDoublePathSum); return returnType(maxSinglePathSum, maxDoublePathSum);
}
};