Easy understand 34ms c++ DFS solution


  • 7
    S
    class Solution {
    private:
        int dfs(TreeNode* root, int& maxsum) {
            if(!root) return 0;
            int l = max(0,dfs(root->left,maxsum));
            int r = max(0,dfs(root->right,maxsum));
            maxsum = max(l+r+root->val, maxsum);
            return root->val + max(l,r);
        }
    public:
        int maxPathSum(TreeNode* root) {
            int maxsum = INT_MIN;
            dfs(root,maxsum);
            return maxsum;
        }
    };

  • 0

    Brilliant and simple solution, kudos


Log in to reply
 

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