C++ 12ms Recursive solution with explanation


  • 0
    S

    Sharing my solution that I came up with. Apparently its about the same as others using but I hope I have a better naming so its easier to understand.

    So in general the idea is to simplify the problem and go little by little.
    Imagine you have a tree line this [4, 1, 2]. which one you would pick? 4 vs 3 (current/root is 4 and children sum is 3).
    If you make more complicated tree, you have to go from low level up to the root and apply same logic recursively. but now you have to keep these 2 values that we were choosing in the first example because if we have tree like this [2, 4, null, 1, 2] (where we added 2 into the root) now we need to choose between 2+3 vs 4 ( 3 is the sum from lower subtree right?)

    So here I have a little helper function that returns the current value what I would choose but also have to return the value that I was comparing to.

    NOTE: that if previous value is bigger than current, you would return prev anyway skipping the current. this will be the case when you have tree like [2, 4, 1]

    void robHelper(TreeNode* node, int &curr, int &prev)
        {
            curr = node->val;
            
            // check if we have prev values
            int currLeft = 0;
            int prevLeft = 0;
            
            // if we can rob left branch
            if (node->left != NULL)
            {
                robHelper(node->left, currLeft, prevLeft);
                curr += prevLeft;
                prev += currLeft;
            }
            
            int currRight = 0;
            int prevRight = 0;
            if (node->right != NULL)
            {
                robHelper(node->right, currRight, prevRight);
                curr += prevRight;
                prev += currRight;
            }
            
            if (prev > curr)
                curr = prev;
        }
        
        int rob(TreeNode* root)
        {
            if (root == NULL)
                return 0;
                
            int curr = 0;
            int prev = 0;
            
            robHelper(root, curr, prev);
            
            return curr;
        }
    

    Feel free to ask question if you are still confused.


Log in to reply
 

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