面试题 04.12. 求和路径
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
3 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
提示：
节点总数 <= 10000原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 16.4 MB, 提交时间: 2022-11-30 21:36:11
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
prefix = collections.defaultdict(int)
prefix[0] = 1
def dfs(root, curr):
if not root:
return 0
ret = 0
curr += root.val
ret += prefix[curr - sum]
prefix[curr] += 1
ret += dfs(root.left, curr)
ret += dfs(root.right, curr)
prefix[curr] -= 1
return ret
return dfs(root, 0)
golang 解法, 执行用时: 4 ms, 内存消耗: 4 MB, 提交时间: 2022-11-30 21:35:51
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, sum int) (ans int) {
preSum := map[int64]int{0: 1}
var dfs func(*TreeNode, int64)
dfs = func(node *TreeNode, curr int64) {
if node == nil {
return
}
curr += int64(node.Val)
ans += preSum[curr-int64(sum)]
preSum[curr]++
dfs(node.Left, curr)
dfs(node.Right, curr)
preSum[curr]--
return
}
dfs(root, 0)
return
}
javascript 解法, 执行用时: 68 ms, 内存消耗: 43.7 MB, 提交时间: 2022-11-30 21:35:31
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number}
*/
var pathSum = function(root, sum) {
const prefix = new Map();
prefix.set(0, 1);
return dfs(root, prefix, 0, sum);
}
const dfs = (root, prefix, curr, sum) => {
if (root == null) {
return 0;
}
let ret = 0;
curr += root.val;
ret = prefix.get(curr - sum) || 0;
prefix.set(curr, (prefix.get(curr) || 0) + 1);
ret += dfs(root.left, prefix, curr, sum);
ret += dfs(root.right, prefix, curr, sum);
prefix.set(curr, (prefix.get(curr) || 0) - 1);
return ret;
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 43.4 MB, 提交时间: 2022-11-30 21:35:15
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number}
*/
var pathSum = function(root, sum) {
if (root == null) {
return 0;
}
let ret = rootSum(root, sum);
ret += pathSum(root.left, sum);
ret += pathSum(root.right, sum);
return ret;
};
const rootSum = (root, sum) => {
let ret = 0;
if (root == null) {
return 0;
}
const val = root.val;
if (val === sum) {
ret++;
}
ret += rootSum(root.left, sum - val);
ret += rootSum(root.right, sum - val);
return ret;
}
golang 解法, 执行用时: 8 ms, 内存消耗: 3.6 MB, 提交时间: 2022-11-30 21:35:00
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rootSum(root *TreeNode, sum int) (res int) {
if root == nil {
return
}
val := root.Val
if val == sum {
res++
}
res += rootSum(root.Left, sum-val)
res += rootSum(root.Right, sum-val)
return
}
func pathSum(root *TreeNode, sum int) int {
if root == nil {
return 0
}
res := rootSum(root, sum)
res += pathSum(root.Left, sum)
res += pathSum(root.Right, sum)
return res
}
python3 解法, 执行用时: 196 ms, 内存消耗: 16.5 MB, 提交时间: 2022-11-30 21:34:45
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
def rootSum(root, sum):
if root is None:
return 0
ret = 0
if root.val == sum:
ret += 1
ret += rootSum(root.left, sum - root.val)
ret += rootSum(root.right, sum - root.val)
return ret
if root is None:
return 0
ret = rootSum(root, sum)
ret += self.pathSum(root.left, sum)
ret += self.pathSum(root.right, sum)
return ret