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; } }; 转载自：http://blog.csdn.net/niaokedaoren/article/details/8798528

 

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

---

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