Simple C++ solution


  • 47
    E
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int tryRob(TreeNode* root, int& l, int& r) {
            if (!root)
                return 0;
                
            int ll = 0, lr = 0, rl = 0, rr = 0;
            l = tryRob(root->left, ll, lr);
            r = tryRob(root->right, rl, rr);
            
            return max(root->val + ll + lr + rl + rr, l + r);
        }
    
        int rob(TreeNode* root) {
            int l, r;
            return tryRob(root, l, r);
        }
    };
    

    Basically you want to compare which one is bigger between 1) you + sum of your grandchildren and 2) sum of your children. Personally I like my solution better than the most voted solution because I don't need complex data structures like map.


  • 0
    M

    excellent.man could u please explain more clear?


  • 0
    G

    ll, lr, rl, rr are the money stolen from the root's grandchildren.

    l and r are the money stolen from the root's children.

    Compare the sum of the money from the root and its grandchildren with the sum of the money from the root's children then return the larger.


  • 2
    D

    Did your answer include this case: the max sum is from rightChild plus leftChild's rightChild?


  • 11
    B

    It will be much more clear if using meaningful variable names.

    static int max(int a, int b) {
        return a > b ? a : b;
    }
     
    static void maxMoney(struct TreeNode* root, int *withMe, int *withoutMe) {
        int wMeL, woMeL; // max money robbed: (with/without me for left child)
        int wMeR, woMeR; // max money robbed: (with/without me for right child)
        
        if (!root)
            return;
        wMeL = woMeL = wMeR = woMeR = 0;
        maxMoney(root->left, &wMeL, &woMeL);
        maxMoney(root->right, &wMeR, &woMeR);
        *withMe = woMeL + woMeR + root->val;
        *withoutMe = max(wMeL, woMeL) + max(wMeR, woMeR);
    }
     
    int rob(struct TreeNode* root) {
        int withMe, withoutMe;
    
        withMe = withoutMe = 0;
        maxMoney(root, &withMe, &withoutMe);
        return max(withMe, withoutMe);
    }

  • 3
    K

    It took me days and 80 lines of python code to get this working and your solution is so ridiculously simple and elegant it makes my code look like garbage. Great job!


  • 0
    S

    I like this one!


  • 0
    L

    what about this tree?
    [1; 10000, 1; 1, 1, 10000, 1], the max should include both child and grandchild,,,


  • 0
    E

    @Lijian In this case in your left tree you will pick left tree itself (10000) and your right tree will pick their children (10000 + 1). Note that 'l' and 'r' is not direct value of your children, but the maximum value that subtree can have.


  • 0
    J

    @espuer like your solution. typical dfs algorithm.


  • 1
    A

    @braydenCN This one is quite clear!


  • 1

    Similar solution but different reasoning.

    class Solution {
    private:
        int rob(TreeNode* root, int &robMax, int &notRobMax) {
            if (!root) return 0;
            int leftRobMax = 0, leftNotRobMax = 0, rightRobMax = 0, rightNotRobMax = 0;
            int leftMax = rob(root->left, leftRobMax, leftNotRobMax);
            int rightMax = rob(root->right, rightRobMax, rightNotRobMax);
            robMax = root->val + leftNotRobMax + rightNotRobMax;
            notRobMax = leftMax + rightMax;
            return max(robMax, notRobMax);
        }
    public:
        int rob(TreeNode* root) {
            int robMax = 0, notRobMax = 0;
            return rob(root, robMax, notRobMax);
        }
    };
    

  • 0
    J

    May I ask why use reference of integers here?
    ll,lr,rl,rr are always 0 here. Why bother declare them? Thank you!


Log in to reply
 

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