{"id":2332,"date":"2018-03-24T02:05:30","date_gmt":"2018-03-24T09:05:30","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2332"},"modified":"2018-03-24T02:30:26","modified_gmt":"2018-03-24T09:30:26","slug":"leetcode-437-path-sum-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-437-path-sum-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 437. Path Sum III"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>\u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u8fd4\u56de\u5355\u5411\u7684\u8def\u5f84\u548c\u7b49\u4e8esum\u7684\u8def\u5f84\u6570\u91cf\u3002<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/path-sum-iii\/description\/\">https:\/\/leetcode.com\/problems\/path-sum-iii\/description\/<\/a><\/p>\n<p>You are given a binary tree in which each node contains an integer value.<\/p>\n<p>Find the number of paths that sum to a given value.<\/p>\n<p>The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).<\/p>\n<p>The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.<\/p>\n<h2><b>Example:<\/b><\/h2>\n<pre class=\"crayon:false\">root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8\r\n\r\n      10\r\n     \/  \\\r\n    <b>5<\/b>   <b>-3<\/b>\r\n   <b>\/<\/b> <b>\\<\/b>    <b>\\<\/b>\r\n  <b>3<\/b>   <b>2<\/b>   <b>11<\/b>\r\n \/ \\   <b>\\<\/b>\r\n3  -2   <b>1<\/b>\r\n\r\nReturn 3. The paths that sum to 8 are:\r\n\r\n1.  5 -&gt; 3\r\n2.  5 -&gt; 2 -&gt; 1\r\n3. -3 -&gt; 11<\/pre>\n<h1>Solution 1<strong>: Recursion<\/strong><\/h1>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(n)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 21 ms\r\nclass Solution {\r\npublic:\r\n  int pathSum(TreeNode* root, int sum) {\r\n    if (!root) return 0;\r\n    return numberOfPaths(root, sum) + pathSum(root-&gt;left, sum) + pathSum(root-&gt;right, sum);\r\n  }\r\nprivate:\r\n  int numberOfPaths(TreeNode* root, int left) {\r\n    if (!root) return 0;    \r\n    left -= root-&gt;val;\r\n    return (left == 0 ? 1 : 0) + numberOfPaths(root-&gt;left, left) + numberOfPaths(root-&gt;right, left);\r\n  }\r\n};<\/pre>\n<h1><strong>Solution 2: Running Prefix Sum<\/strong><\/h1>\n<p>Same idea to\u00a0<a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-560-subarray-sum-equals-k\/\">\u82b1\u82b1\u9171 LeetCode 560. Subarray Sum Equals K<\/a><\/p>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(h)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 13 ms (beats 97.74%)\r\npublic:\r\n  int pathSum(TreeNode* root, int sum) {\r\n    ans_ = 0;\r\n    sums_ = {{0, 1}};\r\n    pathSum(root, 0, sum);\r\n    return ans_;\r\n  }\r\nprivate:\r\n  int ans_;\r\n  unordered_map&lt;int, int&gt; sums_;\r\n  \r\n  void pathSum(TreeNode* root, int cur, int sum) {\r\n    if (!root) return;\r\n    cur += root-&gt;val;\r\n    ans_ += sums_[cur - sum];\r\n    ++sums_[cur];\r\n    pathSum(root-&gt;left, cur, sum);\r\n    pathSum(root-&gt;right, cur, sum);\r\n    --sums_[cur];\r\n  }\r\n};<\/pre>\n<h1><strong>Related Problem<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-560-subarray-sum-equals-k\/\">\u82b1\u82b1\u9171 LeetCode 560. Subarray Sum Equals K<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem \u9898\u76ee\u5927\u610f\uff1a\u7ed9\u4f60\u4e00\u68f5\u4e8c\u53c9\u6811\uff0c\u8fd4\u56de\u5355\u5411\u7684\u8def\u5f84\u548c\u7b49\u4e8esum\u7684\u8def\u5f84\u6570\u91cf\u3002 https:\/\/leetcode.com\/problems\/path-sum-iii\/description\/ You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to&#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":[132,200,28],"class_list":["post-2332","post","type-post","status-publish","format-standard","hentry","category-tree","tag-path-sum","tag-prefix-sum","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2332","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=2332"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2332\/revisions"}],"predecessor-version":[{"id":2339,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2332\/revisions\/2339"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2332"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2332"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2332"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}