> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/337.-house-robber-iii-medium.md).

# 337. House Robber III (Medium)

## 1.問題 

* 小偷發現一個新的偷竊地點. 這地方只有一個出入口 "root",  除了"root"之外, 每間房子有一個parent house. 小偷懂了所有的房屋形成binary tree, 相鄰的房子的保全系統是相連的, 而且若相鄰的房子遭破壞時將會自通知警察
* **找出不被報警下可搶得的最大金額**

![](/files/-LHSu3mmhbVCYLeRXdTK)

## 2.想法 

* Dynamic programming
  * 每回合要選擇可以賺最多錢的選項
    * 1.到前前node (left, right)為止所儲存錢 + 這一層的root node的錢
    * 2.到前node (left, right)為止所儲存錢 + 不加這一層的root node的錢
* DFS

## 3.程式碼 

```
/**
 * 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 rob(TreeNode* root) {
        if (!root)
        {
            return 0;
        }
        int maxExcludeRoot = 0;
        return dfs(root, maxExcludeRoot);
    }
private:
        int dfs(TreeNode* root, int& maxExcludeRoot) {
            if (!root)
            {
                maxExcludeRoot = 0;
                return 0;
            }
            int maxExcludeRootRight = 0;
            int maxExcludeRootLeft = 0;
            //Caculate the max value of right, left subtree
            int maxLeft = dfs(root->left, maxExcludeRootLeft);
            int maxRight = dfs(root->right, maxExcludeRootRight);
            //maxIncludeRoot strored value that current value + max value in last last layer
            int maxIncludeRoot = root->val + maxExcludeRootLeft + maxExcludeRootRight;
            //maxExcludeRoot strored max value in last layer
            maxExcludeRoot = maxLeft + maxRight;
            return max(maxIncludeRoot, maxExcludeRoot);
        }
};
```

## 4.Performance

![](/files/-LHT-MoxWVpIxxGiX6bp)