0437. 路径总和 III

## 题目地址(437. 路径总和 III)

https://leetcode-cn.com/problems/path-sum-iii/

## 题目描述

1

2
3

4
5

6
7

8
9

10
11
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
12
13
10
14
/ \
15
5 -3
16
/ \ \
17
3 2 11
18
/ \ \
19
3 -2 1
20
21

22
23
1. 5 -> 3
24
2. 5 -> 2 -> 1
25
3. -3 -> 11
Copied!

• hashmap

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

## 思路

1
/**
2
* Definition for a binary tree node.
3
* function TreeNode(val) {
4
* this.val = val;
5
* this.left = this.right = null;
6
* }
7
*/
8
// the number of the paths starting from self
9
function helper(root, sum) {
10
if (root === null) return 0;
11
const l = helper(root.left, sum - root.val);
12
const r = helper(root.right, sum - root.val);
13
14
return l + r + (root.val === sum ? 1 : 0);
15
}
16
/**
17
* @param {TreeNode} root
18
* @param {number} sum
19
* @return {number}
20
*/
21
var pathSum = function (root, sum) {
22
// 空间复杂度O(n) 时间复杂度介于O(nlogn) 和 O(n^2)
23
// tag: dfs tree
24
if (root === null) return 0;
25
// the number of the paths starting from self
26
const self = helper(root, sum);
27
// we don't know the answer, so we just pass it down
28
const l = pathSum(root.left, sum);
29
// we don't know the answer, so we just pass it down
30
const r = pathSum(root.right, sum);
31
32
return self + l + r;
33
};
Copied! 437.path-sum-iii 437.path-sum-iii-2

## 关键点解析

• 通过 hashmap，以空间换时间
• 对于这种连续的元素求和问题，有一个共同的思路，可以参考这道题目

## 代码

• 语言支持：JS, Python
JS code:
1
/*
2
* @lc app=leetcode id=437 lang=javascript
3
*
4
*  Path Sum III
5
*/
6
/**
7
* Definition for a binary tree node.
8
* function TreeNode(val) {
9
* this.val = val;
10
* this.left = this.right = null;
11
* }
12
*/
13
function helper(root, acc, target, hashmap) {
14
15
16
if (root === null) return 0;
17
let count = 0;
18
acc += root.val;
19
if (acc === target) count++;
20
if (hashmap[acc - target] !== void 0) {
21
count += hashmap[acc - target];
22
}
23
if (hashmap[acc] === void 0) {
24
hashmap[acc] = 1;
25
} else {
26
hashmap[acc] += 1;
27
}
28
const res =
29
count +
30
helper(root.left, acc, target, hashmap) +
31
helper(root.right, acc, target, hashmap);
32
33
// 这里要注意别忘记了
34
hashmap[acc] = hashmap[acc] - 1;
35
36
return res;
37
}
38
39
var pathSum = function (root, sum) {
40
const hashmap = {};
41
return helper(root, 0, sum, hashmap);
42
};
Copied!
Python Code:
1
import collections
2
'''
3
class TreeNode:
4
def __init__(self, val=0, left=None, right=None):
5
self.val = val
6
self.left = left
7
self.right = right
8
'''
9
class Solution:
10
def helper(self,root,acc,target,hashmap):
11
if not root:
12
return 0
13
count=0
14
acc+=root.val
15
if acc==target:
16
count+=1
17
if acc-target in hashmap:
18
count+=hashmap[acc-target]
19
hashmap[acc]+=1
20
if root.left:
21
count+=self.helper(root.left,acc,target,hashmap)
22
if root.right:
23
count+=self.helper(root.right,acc,target,hashmap)
24
hashmap[acc]-=1
25
return count
26
27
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
28
hashmap=collections.defaultdict(lambda:0)
29
return self.helper(root,0,targetSum,hashmap)
Copied!

• 时间复杂度：\$O(N)\$
• 空间复杂度：\$O(N)\$ 