{"id":953,"date":"2025-12-13T21:10:02","date_gmt":"2025-12-13T13:10:02","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=953"},"modified":"2025-12-13T21:10:02","modified_gmt":"2025-12-13T13:10:02","slug":"leetcode-437-%e8%b7%af%e5%be%84%e6%80%bb%e5%92%8c-iii","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=953","title":{"rendered":"LeetCode 437 – \u8def\u5f84\u603b\u548c III"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h1>\n

\u7ed9\u5b9a\u4e00\u4e2a\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9 root \uff0c\u548c\u4e00\u4e2a\u6574\u6570 targetSum \uff0c\u6c42\u8be5\u4e8c\u53c9\u6811\u91cc\u8282\u70b9\u503c\u4e4b\u548c\u7b49\u4e8e targetSum \u7684 \u8def\u5f84 \u7684\u6570\u76ee\u3002<\/p>\n

\u8def\u5f84 \u4e0d\u9700\u8981\u4ece\u6839\u8282\u70b9\u5f00\u59cb\uff0c\u4e5f\u4e0d\u9700\u8981\u5728\u53f6\u5b50\u8282\u70b9\u7ed3\u675f\uff0c\u4f46\u662f\u8def\u5f84\u65b9\u5411\u5fc5\u987b\u662f\u5411\u4e0b\u7684\uff08\u53ea\u80fd\u4ece\u7236\u8282\u70b9\u5230\u5b50\u8282\u70b9\uff09\u3002<\/p>\n

\"\"<\/a><\/p>\n

\u9898\u76ee\u5206\u6790<\/h1>\n

\u524d\u5e8f\u904d\u5386\uff0c\u8bb0\u5f55\u524d\u9762\u8d70\u8fc7\u7684\u7ed3\u70b9\uff0c\u4ee5\u5f53\u524d\u7ed3\u70b9\u4e3a\u7ec8\u70b9\uff0c\u5411\u524d\u7d2f\u52a0\u3002\u4f46\u4f1a\u53d1\u73b0\u5728\u8ba1\u7b97\u7d2f\u52a0\u548c\u8fd9\u91cc\u5b58\u5728\u5f88\u591a\u91cd\u590d\u8ba1\u7b97\uff0c\u65f6\u95f4\u590d\u6742\u5ea6 O(n * n).
\n\u8bbe\u4ece\u6839\u7ed3\u70b9\u5230\u5f53\u524d\u7ed3\u70b9\u7684\u548c\u662f sum\uff0c\u4f7f\u7528 HashMap \u5b58\u50a8\u4ee5\u6839\u7ed3\u70b9\u4e3a\u8d77\u70b9\u7684\u524d\u7f00\u548c\u3002\u7531\u4e8e\u5b58\u5728\u8d1f\u6570\u7684\u7ed3\u70b9\u503c\uff0c\u6240\u4ee5\u540c\u4e00\u4e2a\u524d\u7f00\u548c\u53ef\u80fd\u4f1a\u5b58\u5728\u591a\u4e2a\u3002
\n\u5bf9\u4e8e\u4e00\u4e2a\u7ed3\u70b9\uff0c\u5982\u679c\u5b83\u662f targetSum \u8def\u5f84\u7684\u7ec8\u70b9\uff0c\u90a3\u4e48 targetSum + \u524d\u7f00\u548c = sum\u3002\u56e0\u6b64\u53ea\u8981\u67e5\u770b map \u4e2d\u662f\u5426\u5b58\u5728 sum – targetSum \u5373\u53ef\u3002
\n\u65f6\u95f4\u590d\u6742\u5ea6 O(n)<\/p>\n

Java<\/h1>\n
private int count = 0;\nprivate HashMap<Long, Integer> preSum;\n\n\/\/ \u524d\u5e8f\u904d\u5386 + \u524d\u7f00\u548c\n\/\/ \u65f6\u95f4\u590d\u6742\u5ea6 O(n)\npublic int pathSum(TreeNode root, int targetSum) {\n    count = 0;\n    preSum = new HashMap<>();\n    preSum.put(0L, 1);\n    dfs(root, targetSum, 0);\n    return count;\n}\n\nprivate void dfs(TreeNode root, int targetSum, long sum) {\n    if (root == null) {\n        return;\n    }\n    sum += root.val;\n    count += preSum.getOrDefault(sum - targetSum, 0);\n    preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);\n    dfs(root.left, targetSum, sum);\n    dfs(root.right, targetSum, sum);\n    preSum.put(sum, preSum.getOrDefault(sum, 0) - 1);\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
private val preSum = HashMap<Long, Int>()\nprivate var count = 0\n\nfun pathSum(root: TreeNode?, targetSum: Int): Int {\n    count = 0\n    preSum.clear()\n    preSum[0L] = 1\n    dfs(root, targetSum, 0)\n    return count\n}\n\nprivate fun dfs(root: TreeNode?, targetSum: Int, sum: Long) {\n    if (root == null) {\n        return\n    }\n\n    val newSum = sum + root.`val`\n    count += preSum.getOrDefault(newSum - targetSum, 0)\n    preSum[newSum] = preSum.getOrDefault(newSum, 0) + 1\n    dfs(root.left, targetSum, newSum)\n    dfs(root.right, targetSum, newSum)\n    preSum[newSum] = preSum.getOrDefault(newSum, 0) - 1\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e00\u4e2a\u4e8c\u53c9\u6811\u7684\u6839\u8282\u70b9 root \uff0c\u548c\u4e00\u4e2a\u6574\u6570 targetSum \uff0c\u6c42\u8be5\u4e8c\u53c9\u6811\u91cc\u8282\u70b9\u503c\u4e4b\u548c\u7b49\u4e8e t […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[11,20,33,78],"class_list":["post-953","post","type-post","status-publish","format-standard","hentry","category-algo","tag-dfs","tag-leetcode","tag-33","tag-78"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/953","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=953"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/953\/revisions"}],"predecessor-version":[{"id":954,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/953\/revisions\/954"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=953"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=953"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=953"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}