C++ straightforward solution


  • 0
    X
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int maxPathSum(TreeNode* root) {
            int partialSum=0;
            int maxSum=INT_MIN;
            calculateSum(root, partialSum, maxSum);
            return maxSum;
        }
        
        //partialSum means the maximal sum which contains only current node and only one of its subtree (either left or right)
        void calculateSum(TreeNode * root, int & partialSum, int & maxSum) {
            if(root == NULL) return;
            int leftPartialSum=0;
            if(root->left != NULL)
                calculateSum(root->left, leftPartialSum, maxSum);
            
            int rightPartialSum=0;
            if(root->right != NULL)
                calculateSum(root->right, rightPartialSum, maxSum);
            
            partialSum=max(root->val, max(root->val+leftPartialSum, root->val+rightPartialSum));
            maxSum=max(partialSum, max(maxSum, leftPartialSum+rightPartialSum+root->val));
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.