classSolution{public:intmaxPathSum(TreeNode*root){intans=INT_MIN;maxPathSumDownFrom(root,ans);returnans;}private:// root->val + 0/1 of its subtreesintmaxPathSumDownFrom(TreeNode*root,int&ans){if(root==nullptr)return0;constintl=max(0,maxPathSumDownFrom(root->left,ans));constintr=max(0,maxPathSumDownFrom(root->right,ans));ans=max(ans,root->val+l+r);returnroot->val+max(l,r);}};
classSolution{publicintmaxPathSum(TreeNoderoot){maxPathSumDownFrom(root);returnans;}privateintans=Integer.MIN_VALUE;// root->val + 0/1 of its subtreesprivateintmaxPathSumDownFrom(TreeNoderoot){if(root==null)return0;finalintl=Math.max(maxPathSumDownFrom(root.left),0);finalintr=Math.max(maxPathSumDownFrom(root.right),0);ans=Math.max(ans,root.val+l+r);returnroot.val+Math.max(l,r);}}