leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

path-sum.dart (852B)

      1 //Find if there is a path down a binary tree where all of the vals
      2 //added together is equal to the targetSum. 
      3 //The time complexity of this is O(n) because in the worst case 
      4 //the algorithm will visit all nodes.
      5 //Time: 298ms Beats: 61.11%
      6 //Memory: 146.4MB Beats:16.67%
      7 
      8 class Solution {
      9   int goal = 0;
     10   bool found = false;
     11   bool hasPathSum(TreeNode? root, int targetSum) {
     12       goal = targetSum;
     13       recurse(root, 0);
     14       return found;
     15   }
     16   void recurse(TreeNode? node, int current_val){
     17       current_val += node?.val ?? 0;
     18       if(node == null){
     19           return;
     20       }
     21       if(found == true){
     22           return;
     23       }
     24       if(current_val == goal && node.left == null && node.right == null){
     25           found = true;
     26           return;
     27       }
     28       recurse(node?.left , current_val);
     29       recurse(node?.right, current_val);
     30   }
     31 }