Dowemo
0 0 0 0

这里写图片描述

"thought".
By converting the problem into two parts, the first part is the maxsum function, and the maximum result is achieved with different nodes. A second part is the downsum function, because the maxsum function determines the root node, so downsum is responsible for the maximum and maximum paths.
But this approach causes.

class Solution {public:
 int ans;
 int maxPathSum(TreeNode* root) {
 if(!root)return0;
 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)
 {
 return0;
 }
 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);
 }
};

"improved.".
Check the online code, calculate the maximum of the left and right nodes, if the left and right nodes are greater than 0, then don't do it. Finally return to root node, root node plus left subtree, root node plus right subtree maximum number.
这里写图片描述

class Solution {public:
 int ans;
 int maxPathSum(TreeNode* root) {
 if(!root)return0;
 ans=root->val;
 maxsum(root);
 return ans;
 }
 int maxsum(TreeNode* root)
 {
 if(!root) return0;
 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);
 returnmax(root->val, max(root->val + lmax, root->val + rmax));
 }

"improved two.".
Just change the decision statement to the max function, but the speed is significantly improved, from 29ms to 19ms.
这里写图片描述

class Solution {public:
 int ans;
 int maxPathSum(TreeNode* root) {
 if(!root)return0;
 ans=root->val;
 maxsum(root);
 return ans;
 }
 int maxsum(TreeNode* root)
 {
 if(!root) return0;
 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);
 returnmax(root->val, max(root->val + lmax, root->val + rmax));
 }



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs