# 0337. 打家劫舍 III

### 题目地址(337. 打家劫舍 III)

<https://leetcode-cn.com/problems/house-robber-iii/>

### 题目描述

```
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \
     3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.


```

### 前置知识

* 二叉树
* 动态规划

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

和 198.house-robber 类似，这道题也是相同的思路。 只不过数据结构从数组换成了树。

我们仍然是对每一项进行决策：**如果我抢的话，所得到的最大价值是多少。如果我不抢的话，所得到的最大价值是多少。**

* 遍历二叉树，都每一个节点我们都需要判断抢还是不抢。
  * 如果抢了的话， 那么我们不能继续抢其左右子节点
  * 如果不抢的话，那么我们可以继续抢左右子节点，当然也可以不抢。抢不抢取决于哪个价值更大。
* 抢不抢取决于哪个价值更大。

这是一个明显的递归问题，我们使用递归来解决。由于没有重复子问题，因此没有必要 cache ，也没有必要动态规划。

### 关键点

* 对每一个节点都分析，是抢还是不抢

### 代码

语言支持：JS, C++，Java，Python

JavaScript Code：

```js
function helper(root) {
  if (root === null) return [0, 0];
  // 0: rob 1: notRob
  const l = helper(root.left);
  const r = helper(root.right);

  const robed = root.val + l[1] + r[1];
  const notRobed = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);

  return [robed, notRobed];
}
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  const [robed, notRobed] = helper(root);
  return Math.max(robed, notRobed);
};
```

C++ Code:

```
/**
 * 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) {
        pair<int, int> res = dfs(root);
        return max(res.first, res.second);
    }

    pair<int, int> dfs(TreeNode* root)
    {
        pair<int, int> res = {0, 0};
        if(root == NULL)
        {
            return res;
        }

        pair<int, int> left = dfs(root->left);
        pair<int, int> right = dfs(root->right);
        // 0 代表不偷，1 代表偷
        res.first = max(left.first, left.second) + max(right.first, right.second);
        res.second = left.first + right.first + root->val;
        return res;
    }

};
```

Java Code:

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    public int[] dp(TreeNode root)
    {
        int[] res = new int[2];
        if(root == null)
        {
            return res;
        }

        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        // 0 代表不偷，1 代表偷
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = left[0] + right[0] + root.val;
        return res;
    }
}
```

Python Code:

```python

class Solution:
    def rob(self, root: TreeNode) -> int:
        def dfs(node):
            if not node:
                return [0, 0]
            [l_rob, l_not_rob] = dfs(node.left)
            [r_rob, r_not_rob] = dfs(node.right)
            return [node.val + l_not_rob + r_not_rob, max([l_rob, l_not_rob]) +  max([r_rob, r_not_rob])]
        return max(dfs(root))


# @lc code=end

```

**复杂度分析**

* 时间复杂度：$O(N)$，其中 N 为树的节点个数。
* 空间复杂度：$O(h)$，其中 h 为树的高度。

### 相关题目

* [198.house-robber](/leetcode-solution/easy/198.house-robber.md)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

![](https://p.ipic.vip/9n0849.jpg)


---

# Agent Instructions: 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:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/337.house-robber-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.