> 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)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/337.-house-robber-iii-medium.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.