0337. 打家劫舍 III · ttttt

# 0337. 打家劫舍 III ## 題目地址(337. 打家劫舍 III) <https://leetcode-cn.com/problems/house-robber-iii/> ## 題目描述 ``` <pre class="calibre18">``` 在上次打劫完一條街道之后和一圈房屋后，小偷又發現了一個新的可行竊的地區。這個地區只有一個入口，我們稱之為“根”。除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。示例 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： ``` <pre class="calibre18">``` 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: ``` <pre class="calibre18">``` /** * 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: ``` <pre class="calibre18">``` /** * 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: ``` <pre class="calibre18">``` 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)O(N)O(N)，其中 N 為樹的節點個數。 - 空間復雜度：O(h)O(h)O(h)，其中 h 為樹的高度。 ## 相關題目 - [198.house-robber](https://github.com/azl397985856/leetcode/blob/master/problems/198.house-robber.md) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)