C++ very concise recursive solution


  • 8
    L
    int maxSum;
    int maxPathSum(TreeNode* root) {
        maxSum = INT_MIN;
        dfs(root);
        return maxSum;
    }
    // post order
    int dfs(TreeNode *root) {
        if (!root) return 0;
         int l = dfs(root->left);
         int r = dfs(root->right);
         maxSum = max(maxSum, root->val + (l > 0 ? l : 0) + (r > 0 ? r : 0));
         return (max(l, r) > 0 ? max(l, r) : 0) + root->val;
    }

Log in to reply
 

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