C++ DFS solution with some explanation.


  • 0
    C

    The idea is also DFS. From bottom to up, at every node, we have four choices:

    1. the left sub-path ==> node ==> the right sub-path

    2. the left sub-path ==> node ==> upper. The left sub-path may yield a negative sum, in which case we set node->left sub-path to zero.

    3. the right sub-path ==> node ==>upper. The right sub-path may yield a negative sum, in which case we set node->right sub-path to zero.

    4. 0 ==> upper, which means we abandon the entire tree rooted at this node because of a negative sum.

    Noted: Negative node values are possible.

    class Solution
    {
    private:
        int maxPathSum(TreeNode *root, int &ma)
        {
            if (!root)
                return 0;
            int left =  maxPathSum(root->left, ma);
            int right = maxPathSum(root->right, ma);
            ma = max(ma, root->val + left + right);
            return max(max(0, max(left, right)) + root->val, 0);
        }
    
    public:
        int maxPathSum(TreeNode* root)
        {
            if (!root)
                return INT_MIN;  //This INT_MIN is just to comply with the judge.
            
            int ma = root->val;
            
            maxPathSum(root, ma);
            
            return ma;
        }
        
    };

  • 0
    S

    Can you please tell me your thought process in the last two statements of the recursion function, I got stuck at the 70th test case and couldn't wrap my head around the problem until i saw a few solutions.


  • 0
    C

    @sujiths52 No shortcuts but practice practice practice.


Log in to reply
 

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