path-sum-iii.dart (1731B)
1 //Given the root of a binary tree find all permutations of the binary tree that add up to 2 //a given number and return that value. To do this I used recursion, 3 //dynamic programming, and memoization to create branches for each node. 4 //Time: 1612ms Beats: 100% 5 //Memory: 168.9MB Beats: 100% 6 //To improve on this I will incorporate more memoization to make 7 //all explored nodes be memoized thus cutting on time. 8 class Solution { 9 int? original_val; 10 Map<TreeNode? , List<int>> vals = {}; 11 int pathSum(TreeNode? root, int targetSum) { 12 return(get_paths(root,targetSum,0)); 13 } 14 int get_paths(TreeNode? root, int targetSum, int depth){ 15 if(vals.containsKey(root)){ 16 List<int> depth_list = (vals[root] ?? []); 17 if(depth_list.contains(depth)){ 18 return 0; 19 } 20 } 21 if(original_val == null){ 22 original_val = targetSum; 23 } 24 if(root == null){ 25 return 0; 26 } 27 int paths = 0; 28 if(targetSum == root.val){ 29 if(vals[root] != null){ 30 if((vals[root]?.contains(depth)) ?? false){ 31 paths += 0; 32 } 33 else{ 34 paths += 1; 35 vals[root]?.add(depth); 36 } 37 } 38 else{ 39 paths += 1; 40 vals[root] = [depth]; 41 } 42 } 43 if(targetSum != (original_val ?? 0)){ 44 paths += get_paths(root.left , targetSum - root.val, depth + 1); 45 paths += get_paths(root.right , targetSum - root.val, depth + 1); 46 } 47 else{ 48 paths += get_paths(root.left , (original_val ?? 0), 0); 49 paths += get_paths(root.right , (original_val ?? 0) , 0); 50 paths += get_paths(root.left , targetSum - root.val , depth + 1); 51 paths += get_paths(root.right , targetSum - root.val, depth + 1); 52 } 53 return paths; 54 } 55 }