###### tags: `Leetcode` `medium` `dynamic programming` `tree` `dfs` `python` `c++`

# 337. House Robber III

## [題目連結:] https://leetcode.com/problems/house-robber-iii/description/

## 題目:
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called ```root```.

Besides the ```root```, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if **two directly-linked houses were broken into on the same night**.

Given the ```root``` of the binary tree, return the maximum amount of money the thief can rob **without alerting the police**.


## 解題想法:
* Robber同類型題目:
* [198. House Robber](/YIzmiuAqRfm6voICu36IXg)
* [213. House Robber II](/STu5wzC9S0ePgRjfJwJCNQ)

* 此題小偷新花樣:
* 從tree中取值使和最大
* 規則是不能同時取相鄰的兩node
* 遞迴解: time: O(n)
* 分別用字典存，對於拜訪到n節點root時:
* 字典1: **Ro[n]**
* 搶該root,可得到最大值
* 相當於:
* 當前root.val+root的兩個子點不搶
* root.val+nR[root.left]nR[root.right]
* 字典2: **nR[n]**
* 不搶該root,可得到最大值
* 相當於:
* 不搶當前root.val,且對於其root的左右子分別可以選擇搶or不搶
* nR[root]=max(Ro[root.left], nR[root.left])+max(Ro[root.right], nR[root.right])

## Python:

from collections import defaultdict

class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
    def insertLeft(self,node):
        if self.left==None:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

# dp+dfs  time:O(n)
class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        Ro=defaultdict(int) #搶   defaultdict(int)初始為0 就算是map[None]一樣是0
        nR=defaultdict(int) #不搶
        self.dfs(root,Ro,nR)
        return max(Ro[root],nR[root])
    
    def dfs(self,root,Ro,nR):
        if not root:
            return 
        self.dfs(root.left,Ro,nR)
        self.dfs(root.right,Ro,nR)
        Ro[root]=root.val+nR[root.left]+nR[root.right]
        nR[root]=max(Ro[root.left],nR[root.left])+max(Ro[root.right],nR[root.right])

root=TreeNode(3)
root.insertLeft(2)
root.insertRight(3)
root.left.insertRight(3)
root.right.insertRight(1)
root.printTree()

result=Solution()
ans=result.rob(root)
print(ans)

## C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rob(TreeNode* root) {
        dfs(root);
        return max(Ro[root], nR[root]);
    }

    void dfs(TreeNode* root){
        if (!root)
            return;
        dfs(root->left);
        dfs(root->right);
        Ro[root]= root->val+ nR[root->left]+ nR[root->right];
        nR[root]= max(Ro[root->left], nR[root->left])+ max(Ro[root->right], nR[root->right]); 
    }
private:
    unordered_map<TreeNode* ,int> Ro, nR; 
};