LeetCode 437. Path Sum III

原题链接在这里：https://leetcode.com/problems/path-sum-iii/

题目：

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  
    5   -3
   /     
  3   2   11
 /    
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

题解：

采用DFS, DFS state needs current node and current sum.

DFS returns count of paths from current node.

PathSum returns dfs from current node + PathSum left child with sum, + PathSum right child with sum.

Time Complexity: O(n^2). Space: O(logn), stack space.

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int pathSum(TreeNode root, int sum) {
12         if(root == null){
13             return 0;
14         }
15         return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
16     }
17     
18     private int dfs(TreeNode root, int sum){
19         int res = 0;
20         if(root == null){
21             return res;
22         }
23         
24         sum -= root.val;
25         if(sum == 0){
26             res++;
27         }
28         res += dfs(root.left, sum) + dfs(root.right, sum);
29         return res;
30     }
31 }

用HashMap来maintain prefix sum. Key 是prefix sum, value 是加到prefix sum的method count.

当cur - sum的值正好出现在prefix中时说明 cur-prefix正好是sum, 从prefix到cur的这一段加起来正好是sum.

Note: put (0, 1) in the map at the beginning. Remember the backtracking, revert the map.

Time Complexity: O(n). Space: O(n), hm.size().

AC Java:

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int pathSum(TreeNode root, int sum) {
12         HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
13         hm.put(0, 1); //设置prefix sum为0的default value是1.
14         return pathSumHelper(root, sum, 0, hm);
15     }
16     
17     private int pathSumHelper(TreeNode root, int sum, int cur, HashMap<Integer, Integer> hm){
18         if(root == null){
19             return 0;
20         }
21         cur += root.val;
22         int res = hm.getOrDefault(cur-sum, 0);
23         
24         hm.put(cur, hm.getOrDefault(cur, 0)+1);
25         res += pathSumHelper(root.left, sum, cur, hm) + pathSumHelper(root.right, sum, cur, hm);
26         hm.put(cur, hm.get(cur)-1); //remove count by 1, backtracking要算其他branch时先回复原值
27         
28         return res;
29     }
30 }

类似Path Sum II, Path Sum IV.