{"id":2105,"date":"2018-03-15T22:18:31","date_gmt":"2018-03-16T05:18:31","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2105"},"modified":"2018-03-15T22:41:27","modified_gmt":"2018-03-16T05:41:27","slug":"leetcode-337-house-robber-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-337-house-robber-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 337. House Robber III"},"content":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u4e0d\u80fd\u540c\u65f6\u53d6\u4e24\u4e2a\u76f8\u90bb\u7684\u8282\u70b9(parent\/child)\uff0c\u95ee\u6700\u591a\u80fd\u53d6\u5f97\u7684\u8282\u70b9\u7684\u503c\u7684\u548c\u662f\u591a\u5c11\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/house-robber-iii\/description\/\">https:\/\/leetcode.com\/problems\/house-robber-iii\/description\/<\/a><\/p>\n<p>The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the &#8220;root.&#8221; Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that &#8220;all houses in this place forms a binary tree&#8221;. It will automatically contact the police if two directly-linked houses were broken into on the same night.<\/p>\n<p>Determine the maximum amount of money the thief can rob tonight without alerting the police.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\" crayon=\"false\">     <span style=\"color: red;\">3<\/span>\r\n    \/ \\\r\n   2   3\r\n    \\   \\ \r\n     <span style=\"color: red;\">3   1<\/span>\r\n<\/pre>\n<p>Maximum amount of money the thief can rob =\u00a0<span style=\"color: red;\">3<\/span>\u00a0+\u00a0<span style=\"color: red;\">3<\/span>\u00a0+\u00a0<span style=\"color: red;\">1<\/span>\u00a0=\u00a0<b>7<\/b>.<\/p>\n<p><b>Example 2:<\/b><\/p>\n<pre class=\"crayon:false \">     3\r\n    \/ \\\r\n   <span style=\"color: red;\">4<\/span>   <span style=\"color: red;\">5<\/span>\r\n  \/ \\   \\ \r\n 1   3   1\r\n<\/pre>\n<p>Maximum amount of money the thief can rob =\u00a0<span style=\"color: red;\">4<\/span>\u00a0+\u00a0<span style=\"color: red;\">5<\/span>\u00a0=\u00a0<b>9<\/b>.<\/p>\n<p><strong>Idea:\u00a0<\/strong><\/p>\n<p>Compare grandparent + max of grandchildren(l.l + l.r + r.l + r.r) vs max of children (l + r)<\/p>\n<p><b>Solution 1: Recursion w\/o memorization\u00a0<\/b><\/p>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 1289 ms\r\nclass Solution {\r\npublic:\r\n  int rob(TreeNode* root) {\r\n    if (root == nullptr) return 0;\r\n    int val = root-&gt;val;\r\n    int ll = root-&gt;left ? rob(root-&gt;left-&gt;left) : 0;\r\n    int lr = root-&gt;left ? rob(root-&gt;left-&gt;right) : 0;\r\n    int rl = root-&gt;right ? rob(root-&gt;right-&gt;left) : 0;\r\n    int rr = root-&gt;right ? rob(root-&gt;right-&gt;right) : 0;\r\n    return max(val + ll + lr + rl + rr, rob(root-&gt;left) + rob(root-&gt;right));\r\n  }\r\n};<\/pre>\n<p><strong>Solution 2:\u00a0<\/strong><b>Recursion w\/ memorization\u00a0<\/b><\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 15 ms\r\nclass Solution {\r\npublic:\r\n  int rob(TreeNode* root) {\r\n    if (root == nullptr) return 0;\r\n    if (m_.count(root)) return m_[root];\r\n    int val = root-&gt;val;\r\n    int ll = root-&gt;left ? rob(root-&gt;left-&gt;left) : 0;\r\n    int lr = root-&gt;left ? rob(root-&gt;left-&gt;right) : 0;\r\n    int rl = root-&gt;right ? rob(root-&gt;right-&gt;left) : 0;\r\n    int rr = root-&gt;right ? rob(root-&gt;right-&gt;right) : 0;\r\n    return m_[root] = max(val + ll + lr + rl + rr, rob(root-&gt;left) + rob(root-&gt;right));\r\n  }\r\nprivate:\r\n  unordered_map&lt;TreeNode*, int&gt; m_;\r\n};<\/pre>\n<p><strong>Solution 3: Recursion return children&#8217;s value<\/strong><\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 10 ms (beats 97.57%)\r\nclass Solution {\r\npublic:\r\n  int rob(TreeNode* root) {\r\n    int l = 0;\r\n    int r = 0;\r\n    return rob(root, l, r);    \r\n  }\r\nprivate:\r\n  \/\/ return rob(root) and stores rob(root-&gt;left\/right) in l\/r.\r\n  int rob(TreeNode* root, int&amp; l, int&amp; r) {\r\n    if (root == nullptr) return 0;\r\n    int ll = 0;\r\n    int lr = 0;\r\n    int rl = 0;\r\n    int rr = 0;\r\n    l = rob(root-&gt;left, ll, lr);\r\n    r = rob(root-&gt;right, rl, rr);    \r\n    return max(root-&gt;val + ll + lr + rl + rr, l + r);\r\n  }\r\n};<\/pre>\n<p>Python3<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 64 ms (beats 93.18%)\r\n\"\"\"\r\nclass Solution:\r\n  def rob(self, root):\r\n    def rob(root):\r\n      if not root: return 0, 0, 0\r\n      l, ll, lr = rob(root.left)\r\n      r, rl, rr = rob(root.right)\r\n      return max(root.val + ll + lr + rl + rr, l + r), l, r\r\n    \r\n    return rob(root)[0]<\/pre>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-198-house-robber\/\">\u82b1\u82b1\u9171 LeetCode 198. House Robber<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u4e0d\u80fd\u540c\u65f6\u53d6\u4e24\u4e2a\u76f8\u90bb\u7684\u8282\u70b9(parent\/child)\uff0c\u95ee\u6700\u591a\u80fd\u53d6\u5f97\u7684\u8282\u70b9\u7684\u503c\u7684\u548c\u662f\u591a\u5c11\u3002 Problem: 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 the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[30,177,17],"class_list":["post-2105","post","type-post","status-publish","format-standard","hentry","category-tree","tag-binary-tree","tag-medium","tag-recursion","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2105","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2105"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2105\/revisions"}],"predecessor-version":[{"id":2113,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2105\/revisions\/2113"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2105"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2105"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2105"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}