【NewCode-LeetCode】binary-tree-maximum-path-sum

题目：传送门

题意：

问题就类似于在一个无向图中，以某个点为起点，以另一个点为终点，使其从起点到终点的路劲和最大，而这里就是把无向图变成了二叉树。

思路

①可以发现这道题是分而治之的思想，其实做得多了会发现很多二叉树的问题都是分而治之的思想；要得出二叉树的最大值（这里就默认指最大路径和的值），先得算出左子树的最大值和右子树的最大值；而左子树的最大值又需要先算出它的左子树的最大值和右子树的最大值，右子树的最大值也是先算出它的左子树的最大值和右子树的最大值，…

②最后分呀分呀就分到了叶子结点，而叶子节点的左子树和右子树都是0，这个时候走到头了，我们就该往回走了，开始慢慢的向上解决问题；知道左子树和右子树的值了之后（这里需要注意的是如果左子树或右子树的值是小于0的，则我们取0，小于0我们就不能走这里，不然最大值反而会越加越小），我们就可以得出当前节点的最大值：Max ( left , right ) + 当前节点的值；

③but 到这还没完，有可能当前节点 + 左子树的值left + 右子树的值right 就是最大值，因此还需要将 left + right + 当前节点的值和最终值 ans 进行比较，如果比ans大时，就将这个值赋给ans

代码

/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int ans = -999999999; int getMax(TreeNode* root){ if(!root) return 0; int left = max(0, getMax(root->left)); //左子树 最大和 int right = max(0, getMax(root->right)); //右子树 最大和 ans = max(ans, left+right+root->val); //每次ans都要 和当前小子树的 和进行比较（判断此子树的和值就是最大值） return max(left, right) + root->val; } int maxPathSum(TreeNode* root) { // write code here return max(ans, getMax(root)); } };