Simple C++ recursive solution


  • 0
    X
    class Solution {
    public:
        int maxPathSum(TreeNode* root) {
            int result = INT_MIN;
            helper(root, result);
            return result;
        }
        
        int helper(TreeNode* root, int& result) {
            if (NULL == root) return 0;
            else {
                int leftSum = helper(root->left, result);
                int rightSum = helper(root->right, result);
                
                leftSum = leftSum > 0 ? leftSum : 0;
                rightSum = rightSum > 0 ? rightSum : 0;
                
                result = max(result, root->val + leftSum + rightSum);
                return root->val + max(leftSum, rightSum);
            }
        }
    };
    

Log in to reply
 

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