Welcome to Subscribe On Youtube
437. Path Sum III
Description
Given the root
of a binary tree and an integer targetSum
, return the number of paths where the sum of the values along the path equals targetSum
.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).
Example 1:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 Output: 3 Explanation: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3
Constraints:
- The number of nodes in the tree is in the range
[0, 1000]
. -109 <= Node.val <= 109
-1000 <= targetSum <= 1000
Solutions
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private Map<Long, Integer> cnt = new HashMap<>(); private int targetSum; public int pathSum(TreeNode root, int targetSum) { cnt.put(0L, 1); this.targetSum = targetSum; return dfs(root, 0); } private int dfs(TreeNode node, long s) { if (node == null) { return 0; } s += node.val; int ans = cnt.getOrDefault(s - targetSum, 0); cnt.merge(s, 1, Integer::sum); ans += dfs(node.left, s); ans += dfs(node.right, s); cnt.merge(s, -1, Integer::sum); return ans; } }
-
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int pathSum(TreeNode* root, int targetSum) { unordered_map<long, int> cnt; cnt[0] = 1; function<int(TreeNode*, long)> dfs = [&](TreeNode* node, long s) -> int { if (!node) return 0; s += node->val; int ans = cnt[s - targetSum]; ++cnt[s]; ans += dfs(node->left, s) + dfs(node->right, s); --cnt[s]; return ans; }; return dfs(root, 0); } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: def dfs(node, s): if node is None: return 0 s += node.val ans = cnt[s - targetSum] cnt[s] += 1 ans += dfs(node.left, s) ans += dfs(node.right, s) cnt[s] -= 1 return ans cnt = Counter({0: 1}) return dfs(root, 0)
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func pathSum(root *TreeNode, targetSum int) int { cnt := map[int]int{0: 1} var dfs func(*TreeNode, int) int dfs = func(node *TreeNode, s int) int { if node == nil { return 0 } s += node.Val ans := cnt[s-targetSum] cnt[s]++ ans += dfs(node.Left, s) + dfs(node.Right, s) cnt[s]-- return ans } return dfs(root, 0) }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function pathSum(root: TreeNode | null, targetSum: number): number { const cnt: Map<number, number> = new Map(); const dfs = (node: TreeNode | null, s: number): number => { if (!node) { return 0; } s += node.val; let ans = cnt.get(s - targetSum) ?? 0; cnt.set(s, (cnt.get(s) ?? 0) + 1); ans += dfs(node.left, s); ans += dfs(node.right, s); cnt.set(s, (cnt.get(s) ?? 0) - 1); return ans; }; cnt.set(0, 1); return dfs(root, 0); }
-
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} targetSum * @return {number} */ var pathSum = function (root, targetSum) { const cnt = new Map(); const dfs = (node, s) => { if (!node) { return 0; } s += node.val; let ans = cnt.get(s - targetSum) || 0; cnt.set(s, (cnt.get(s) || 0) + 1); ans += dfs(node.left, s); ans += dfs(node.right, s); cnt.set(s, cnt.get(s) - 1); return ans; }; cnt.set(0, 1); return dfs(root, 0); };
-
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int PathSum(TreeNode root, int targetSum) { Dictionary<long, int> cnt = new Dictionary<long, int>(); int Dfs(TreeNode node, long s) { if (node == null) { return 0; } s += node.val; int ans = cnt.GetValueOrDefault(s - targetSum, 0); cnt[s] = cnt.GetValueOrDefault(s, 0) + 1; ans += Dfs(node.left, s); ans += Dfs(node.right, s); cnt[s]--; return ans; } cnt[0] = 1; return Dfs(root, 0); } }
-
// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: Option<Rc<RefCell<TreeNode>>>, // pub right: Option<Rc<RefCell<TreeNode>>>, // } // // impl TreeNode { // #[inline] // pub fn new(val: i32) -> Self { // TreeNode { // val, // left: None, // right: None // } // } // } use std::cell::RefCell; use std::collections::HashMap; use std::rc::Rc; impl Solution { pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 { let mut cnt = HashMap::new(); cnt.insert(0, 1); fn dfs( node: Option<Rc<RefCell<TreeNode>>>, s: i64, target: i64, cnt: &mut HashMap<i64, i32>, ) -> i32 { if let Some(n) = node { let n = n.borrow(); let s = s + n.val as i64; let ans = cnt.get(&(s - target)).copied().unwrap_or(0); *cnt.entry(s).or_insert(0) += 1; let ans = ans + dfs(n.left.clone(), s, target, cnt) + dfs(n.right.clone(), s, target, cnt); *cnt.get_mut(&s).unwrap() -= 1; ans } else { 0 } } dfs(root, 0, target_sum as i64, &mut cnt) } }