/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
// the number of the paths starting from self
function helper(root, sum) {
if (root === null) return 0;
const l = helper(root.left, sum - root.val);
const r = helper(root.right, sum - root.val);
return l + r + (root.val === sum ? 1 : 0);
}
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number}
*/
var pathSum = function (root, sum) {
// 空间复杂度O(n) 时间复杂度介于O(nlogn) 和 O(n^2)
// tag: dfs tree
if (root === null) return 0;
// the number of the paths starting from self
const self = helper(root, sum);
// we don't know the answer, so we just pass it down
const l = pathSum(root.left, sum);
// we don't know the answer, so we just pass it down
const r = pathSum(root.right, sum);
return self + l + r;
};
另外我画了一个图，相信看完你就明白了。
当我们执行到底部的时候：
接着往上回溯：
很容易看出，我们的 hashmap 不应该有第一张图的那个记录了，因此需要减去。
具体实现见下方代码区。
关键点解析
通过 hashmap，以空间换时间
代码
语言支持：JS, Python
JS code:
/*
* @lc app=leetcode id=437 lang=javascript
*
* [437] Path Sum III
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
function helper(root, acc, target, hashmap) {
// see also : https://leetcode.com/problems/subarray-sum-equals-k/
if (root === null) return 0;
let count = 0;
acc += root.val;
if (acc === target) count++;
if (hashmap[acc - target] !== void 0) {
count += hashmap[acc - target];
}
if (hashmap[acc] === void 0) {
hashmap[acc] = 1;
} else {
hashmap[acc] += 1;
}
const res =
count +
helper(root.left, acc, target, hashmap) +
helper(root.right, acc, target, hashmap);
// 这里要注意别忘记了
hashmap[acc] = hashmap[acc] - 1;
return res;
}
var pathSum = function (root, sum) {
const hashmap = {};
return helper(root, 0, sum, hashmap);
};
Python Code:
import collections
'''
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
'''
class Solution:
def helper(self,root,acc,target,hashmap):
if not root:
return 0
count=0
acc+=root.val
if acc==target:
count+=1
if acc-target in hashmap:
count+=hashmap[acc-target]
hashmap[acc]+=1
if root.left:
count+=self.helper(root.left,acc,target,hashmap)
if root.right:
count+=self.helper(root.right,acc,target,hashmap)
hashmap[acc]-=1
return count
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
hashmap=collections.defaultdict(lambda:0)
return self.helper(root,0,targetSum,hashmap)
复杂度分析
时间复杂度：$O(N)$
空间复杂度：$O(N)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
