• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode-437 – Sum of paths III

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given the root node of a binary tree and an integer targetSum, find the number of paths in the binary tree where the sum of the node values equals targetSum.

The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from parent to child).

 

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8Copy the code

Example 2:

Input: root = [13,4,7,2 5,4,8,11, null, null, null, 5, 1], targetSum = 22 output: 3Copy the code

Tip:

  • The number of nodes in a binary tree ranges from 0 to 1000.
  • -109 <= Node.val <= 109 
  • -1000 <= targetSum <= 1000 

Idea 1: DFS

  • The conventional summation goes down recursively
  • Meet the conditions
public int pathSum(TreeNode root, int targetSum) { target = targetSum; dfsNode(root); return res; } public void dfsNode(TreeNode root) { if (root == null) { return; } dfs(root, root.val); dfsNode(root.left); dfsNode(root.right); } public void dfs(TreeNode root, int tmp) { if (tmp == target) { res += 1; } if (root.left ! = null) { dfs(root.left, tmp + root.left.val); } if (root.right ! = null) { dfs(root.right, tmp + root.right.val); }}Copy the code
  • Time complexity O(
    n 2 n^2     )
  • Space complexity O(n)

Idea 2: Prefix sum

  • The above ideas involve paths of double computation
  • Subtraction can be done by prefixes and sums
  • Map (0,1) is stored first because we need to calculate the nodes.
  • You also need to trace back across node paths
Map<Integer, Integer> map = new HashMap<>(); public int pathSum(TreeNode root, int targetSum) { if (root == null) { return 0; } target = targetSum; map.put(0, 1); dfs(root, map, 0); return res; } public void dfs(TreeNode root, Map<Integer, Integer> map, int tmp) { if (root == null) { return; } tmp += root.val; res += map.getOrDefault(tmp - target, 0); map.put(tmp, map.getOrDefault(tmp, 0) + 1); if (root.left ! = null) dfs(root.left, map, tmp); if (root.right ! = null) dfs(root.right, map, tmp ); // Backtrace map.put(TMP, map.getorDefault (TMP, 0) -1); }Copy the code
  • Time complexity O(n)
  • Space complexity O(n)