Home raiding III (leetcode-337)

raid homes and plunder houses Ⅲ（LeetCode-337）

subject

The thief found a new area to steal . There is only one entrance to the area , We call it root .

except root outside , Each house has and only has one “ Father “ The house is connected to it . After some reconnaissance , The clever thief realized that “ All the houses in this place are arranged like a binary tree ”. If Two directly connected houses were robbed the same night , The house will alarm automatically .

Given a binary tree root . return Without triggering the alarm , The maximum amount a thief can steal .

Example 1:

 Input : root = [3,2,3,null,3,null,1]
 Output : 7 
 explain :  The maximum amount a thief can steal in a night  3 + 3 + 1 = 7

Example 2:

 Input : root = [3,4,5,1,3,null,1]
 Output : 9
 explain :  The maximum amount a thief can steal in a night  4 + 5 = 9 

Tips ：

• The number of nodes in the tree is [1, 104] Within the scope of
• 0 <= Node.val <= 104

Ideas

Tree array

1. Determine the parameters and return values of the recursive function

   • Return the money obtained in two states of stealing and not stealing . Subscript 0 Indicates the maximum amount obtained by not stealing the current node , Subscript 1 Indicates the maximum amount obtained by stealing the current node

2. Determine termination conditions

   • Empty node encountered , Must be returned $\{0,0\}$

3. Determine the traversal order

   • Must traverse in sequence , Because we need to consider after returning the value through the recursive function

4. Determine the single layer logic

   • If you steal the current node

     • Left and right children can't steal , That is, the left and right children take the subscript 0 The value of the combined
       $$val1=cur.val+left[0]+right[0]$$

   • If you don't steal the current node

     • Left and right children can consider stealing , But whether to steal or not depends on
       $$val2=max(left[0],left[1])+max(right[0],right[1])$$

5. The test case

Code display

class Solution
{
    
public:
    int rob(TreeNode *root)
    {
    
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    vector<int> robTree(TreeNode *cur)
    {
    
        if (!cur)
        {
    
            return {
    0, 0};
        }
        vector<int> curleft = robTree(cur->left);
        vector<int> curright = robTree(cur->right);
        int val1 = cur->val + curleft[0] + curright[0];
        int val2 = max(curleft[0], curleft[1]) + max(curright[0], curright[1]);
        return {
    val2, val1};
    }
};