Share my C++ recursive solution


  • 0
    B

    The general idea is easy: find the maximum value between robing son nodes and robbing root node.

    class Solution 
    {
    public:
        int rob(TreeNode* root)
        {
            if(!root) return 0;
            if(!root->left && !root->right) return root->val;
            
            int sonMax = 0;         //Rob son nodes
            int grandsonMax = 0;    //Rob grandson nodes and root node.
            
            //Sum up all son values or grandson values if they exist.
            if(root->left)
            {
                sonMax += rob(root->left);
                grandsonMax += (root->left->left ? rob(root->left->left) : 0) + (root->left->right ? rob(root->left->right) : 0);
            }
            if(root->right)
            {
                sonMax += rob(root->right);
                grandsonMax += (root->right->left ? rob(root->right->left) : 0) + (root->right->right ? rob(root->right->right) : 0);
            }
            
            return max(sonMax, root->val + grandsonMax);
        }
    };

Log in to reply
 

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