1.题目说明

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.

 

2.解法分析：

leetcode中给出的函数头为：int maxPathSum(TreeNode *root)

给定的数据结构为：

Definition for binary tree

* struct TreeNode {

*     int val;

*     TreeNode *left;

*     TreeNode *right;

*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

乍一看这道题我就递归，每一条路径都会有一个最高节点，整棵树的最高节点是root，因此，对整棵树而言，和最长的路径只有三种情况：

• 路径的最高节点为root
• 路径的最高节点在root的左子树中
• 路径的最高节点在root的右子树中

所以，这题可以递归来做，需要考虑的是路径中至少有一个节点，不能是空路径，这会给编码带来一定的麻烦，而且，虽然有了刚才的三个分类，怎么求三种情况下的最长路径呢？我们定义从节点A往下走一直到根部（可以不到根部）的路径中和最大的这个值为rootStartPathMaxSum(A),那么必然有，：

• 如果路径的最高节点经过了root：理论上最大值为max(0,rootStartPathMaxSum(root->left) )+max(0,rootStartPathMaxSum(root->right) ) +root->val；
• 如果路径的最高节点在root，递归计算
• 如果路径的最高节点在root右侧，递归计算

最后比较这三种得出的值即可。

rootStartPathMaxSum(TreeNode *)这个函数的计算我最开始的算法是递归的。于是得出了下面一份代码。

/**

* 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) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if(root == NULL)return 0;

if(root->left == NULL && root->right == NULL)

{

return root->val;

}

int case_both_side = max(0,rootStartPathMaxSum(root->left))+max(0,rootStartPathMaxSum(root->right))+root->val;

if(root->left!=NULL && root->right == NULL)

{

return max(case_both_side,maxPathSum(root->left));

}

if(root->left==NULL && root->right != NULL)

{

return max(case_both_side,maxPathSum(root->right));

}

else

return max(max(maxPathSum(root->left),maxPathSum(root->right)),case_both_side);

}

// 从root开始往根出发的和最长路径，不一定要到达根部

int rootStartPathMaxSum(TreeNode *root)

{

if(root == NULL)return 0;

if(root->left == NULL&& root->right == NULL)return root->val;

if(root->left == NULL && root->right != NULL)

{

return max(root->val,root->val+rootStartPathMaxSum(root->right));

}

if(root->left != NULL && root->right ==NULL)

{

return max(root->val,root->val+rootStartPathMaxSum(root->left));

}

return max(max(rootStartPathMaxSum(root->left)+root->val,rootStartPathMaxSum(root->right)+root->val),root->val);

}

};

 

在小数据集上运行良好，但是一到大数据集就hold不住了，运行结果如下：

其实写的过程就意识到了rootStartPathMaxSum有很多次被重复调用，于是得采用一种自底向上的算法，自己想了半天没想出来，结果网上搜到了一个神代码，我承认，很精妙，记录一下，学习一下：

/**

* 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) {

// Start typing your C/C++ solution below

// DO NOT write int main() function

if (root == NULL)

return 0;

int max = root->val;

getPathSum(root, max);

return max;

}

private:

int getPathSum(TreeNode *root, int &max) {

if (root == NULL)

return 0;

int leftSum = getPathSum(root->left, max);

int rightSum = getPathSum(root->right, max);

if (leftSum + root->val + rightSum > max)

max = leftSum + root->val + rightSum;

int subPathSum = leftSum > rightSum ? leftSum : rightSum;

subPathSum += root->val;

return subPathSum > 0 ? subPathSum : 0;

}

};

转载自：

 

总的来说，我的算法思路跟这位是一样的，可惜实现思路的功底却差了很多，加油！

---

后记： 回去略微思索，上述思路中用一个max记录了当前最大值，leftsum和rightSum正是我所想追求的自底向上的中间变量，学习了，不过我的算法的有点事可以用两个中间变量保存起点和终点，这样就有利于路径记录。