【leetcode】124.Binary Tree Maximum Path Sum

「思路」 将问题转化为两个部分，第一部分为maxsum函数，实现以不同节点作为根节点的最大结果，并不断更新最大结果。第二部分为downsum函数，由于maxsum函数确定了根节点，所以downsum负责以固定点为根节点向下传递时路径最大的和。 但是这种办法导致超时。

class Solution { public: int ans; int maxPathSum(TreeNode* root) { if(!root)return 0; ans=root->val; maxsum(root,ans); return ans; } void maxsum(TreeNode* root,int a) { ans=max(ans,a); if(!root) { return; } int m,n; if(downsum(root->left)<0) {m=0;} else m=downsum(root->left); if(downsum(root->right)<0){n=0;} else n=downsum(root->right); a=root->val+m+n; maxsum(root->left,a); maxsum(root->right,a); } int downsum(TreeNode* root)//问题转化为向下单向传递时，和最大的路径 { if(!root) { return 0; } int m,n; if(downsum(root->left)<0) {m=0;} else m=downsum(root->left); if(downsum(root->right)<0){n=0;} else n=downsum(root->right); return root->val+max(m,n); } };

「改进一」 查了一下网上的代码，先计算出左右节点的最大值，如果左右节点大于0，则加上左右节点，否则不加。最后返回根节点，根节点加左子树，根节点加右子树最大的数。

class Solution { public: int ans; int maxPathSum(TreeNode* root) { if(!root)return 0; ans=root->val; maxsum(root); return ans; } int maxsum(TreeNode* root) { if(!root) return 0; int node=root->val; int lmax=maxsum(root->left),rmax=maxsum(root->right); if(lmax>0)node+=lmax; if(rmax>0)node+=rmax; ans=max(ans,node); return max(root->val, max(root->val + lmax, root->val + rmax)); }

「改进二」 仅仅将判断语句改为max函数，但是速度有了显著提升，从29ms进步到19ms。

class Solution { public: int ans; int maxPathSum(TreeNode* root) { if(!root)return 0; ans=root->val; maxsum(root); return ans; } int maxsum(TreeNode* root) { if(!root) return 0; int node=root->val; int lmax=maxsum(root->left),rmax=maxsum(root->right); node+=max(0,lmax); node+=max(0,rmax); ans=max(ans,node); return max(root->val, max(root->val + lmax, root->val + rmax)); }