Java solution with detailed explanation


  • 0
    L

    I initially got stumped with this question as I didn't pay attention to the minute details. However, I looked at the discussion to understand what I had missed so summing it up for anyone who wants to understand how to approach this problem. So the basic idea of this problem is that the search base may be each and every node of this tree. It may start from the root and you may have to follow to the leaf even though you may have met the sum before. You continue because there may be a negative number in between that will help you get the sum more than once. Like 1 -> -2 -> 1 -> -1, you will find -1 on this route 3 times while traversing from root to the leaf using the sets: (1,-2), (-2,1), (1,-2,1,-1).

    So the idea is to traverse root and recursively traverse both its children till you reach to the leaf.

        AtomicInteger count = new AtomicInteger(0);
        public int pathSum(TreeNode root, int sum) {
            if(root==null) {
                return count.get();
            }
            sum(root,sum,count); 
            pathSum(root.left,sum);
            pathSum(root.right,sum);
            return count.get();
        }
        
        private void sum(TreeNode root,int sum, AtomicInteger count) {
            if(root==null) {
                return;
            }
            
            if(root.val-sum==0) {
                count.getAndIncrement();
            }
            
            sum(root.left,sum-root.val,count);
            sum(root.right,sum-root.val,count);
        }
    

  • 0
    Y
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.