number of paths in a binary tree with a given sum

Question

I am solving the problem https://leetcode.com/problems/path-sum-iii/ I'll also briefly mention it here: Find the number of paths in a Binary tree whose sum = sum. The path does not necessarily have to begin (end) at the root (leaf). As long as the path goes downward it should be considered as a valid path.

Here is my solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public int pathSum(TreeNode root, int sum) {
        int path = 0;
        if(root.val == sum)
            return 1;
        else if(root.left == null && root.right == null)
            return 0;
        if(root.left != null){
            path += pathSum(root.left, sum - root.val);
            path += pathSum(root.left, sum);
        }
        if(root.right != null){
            path += pathSum(root.right, sum - root.val);
            path += pathSum(root.right, sum);
        }
        return path;
    }
}

The answer as per their system is 3, but I am getting the answer as 4 for the following input:

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

I have spent hours trying to reason why my code wold not work, but I cannot figure out the problem.

Sorry for a naive question :( But this is killing me!

Answer 1

The problem with your solution is that it is also counting 10 - 2 = 8. where 10 is the topmost root node and -2 is a bottom leaf. It ignores all the path in between.

I managed to solve it with a tamperedSum boolean.

public static int pathSum(TreeNode root, int sum, boolean tamperedSum)  
{
    int path = 0;
    if(root.val == sum)
        path = 1;

    if(root.left == null && root.right == null)
        return path;

    if(root.left != null){
        path += pathSum(root.left, sum - root.val, true);
        if (!tamperedSum)
            path += pathSum(root.left, sum, false);
    }   
    if(root.right != null){
        path += pathSum(root.right, sum - root.val, true);
        if (!tamperedSum)
            path += pathSum(root.right, sum, false);
    }   
    return path;
}   

The tamperedSum boolean is set to true when we have deducted values (of nodes) from the original sum which in this case is 8.

We would invoke it as:

pathSum(root, sum, false)

The idea is that if the sum has been tampered i.e a node value on the path has already been deducted, we are no longer allowed to pass it as-is to the branch below the node.

So, we set tamperedSum to true whenever we deduct the node value from the sum as: sum - root.value. After that, all nodes below it are not allowed to pass through the sum without deducting their node value from it.

Answer 2

the problem with your solution is that you do not start from an initial sum, if you are in a new inner path.

so you should keep track of both the accomulated sum and the original sum as well when you move inner path.

find below a modified copy of your algorithm.

public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    boolean visitedAsRoot = false;

    TreeNode(int x) {
        val = x;
    }
}

public static int pathSum(TreeNode root, int accomulate, int sum) {
    int path = 0;
    if (root.val == accomulate)
        return 1;
    else if (root.left == null && root.right == null)
        return 0;
    if (root.left != null) {
        path += pathSum(root.left, accomulate - root.val, sum);
        if (!root.left.visitedAsRoot) {
            root.left.visitedAsRoot = true;
            path += pathSum(root.left, sum, sum);
        }
    }
    if (root.right != null) {
        path += pathSum(root.right, accomulate - root.val, sum);
        if (!root.right.visitedAsRoot) {
            root.right.visitedAsRoot = true;
            path += pathSum(root.right, sum, sum);
        }
    }
    return path;
}

public static void main(String args[]) {
    TreeNode t1 = new TreeNode(3);
    TreeNode t2 = new TreeNode(-2);
    TreeNode t3 = new TreeNode(1);
    TreeNode t4 = new TreeNode(3);
    TreeNode t5 = new TreeNode(2);
    TreeNode t6 = new TreeNode(11);
    TreeNode t7 = new TreeNode(5);
    TreeNode t8 = new TreeNode(-3);
    TreeNode t9 = new TreeNode(10);

    t4.left = t1;
    t4.right = t2;

    t5.right = t3;

    t7.left = t4;
    t7.right = t5;

    t8.right = t6;

    t9.left = t7;
    t9.right = t8;

    System.out.println(pathSum(t9, 8, 8));
}

Answer 3

your code cant satisfy this constraint:

these nodes should be continuous.

e.g the root(value 10) of this tree and the leaf(value -2) of this tree, the sum of them is equals 8. but it dont satisfy continous, so It cant count.

Unfortunately, your code cant filter this case.

an alternative Solution:

public class Solution {
public int pathSum(TreeNode root, int sum) {
    int path = traverse(root,sum);
    return path;
}

public int traverse(TreeNode root, int sum){
    int path = 0;
    if(root==null){
        return 0;
    }
    else{
        path += calcu(root,sum);
        path += traverse(root.left,sum);
        path += traverse(root.right,sum);
        return path;
    }
}

private int calcu(TreeNode root, int sum) {
    if(root==null){
        return 0;
    }
    else if(root.val==sum){
        return 1 + calcu(root.left,sum-root.val)+calcu(root.right,sum-root.val);
    }
    else{
        return calcu(root.left,sum-root.val)+calcu(root.right,sum-root.val);
    }
}
}

explanation: traverse this tree and make every treeNode as root node, find target path under the premise continous.

Answer 4

I'm not sure what's wrong in your solution, but I don't think it's correct. For one thing, if your root was 8 you would immediately return and count only the root as solution. This is how I would do it:

import java.util.ArrayList;

public class Solution {
    public static int pathSum(TreeNode root, int sum) {
      return pathSum(root, sum, 0, new ArrayList<Integer>());
    }

    public static int pathSum(TreeNode root, int sum, int count, ArrayList<Integer> arr) {
        arr.add(root.val);
        int acc = 0;
        for (int i=arr.size()-1; i>=0; i--) {
          acc += arr.get(i);
          if (acc == sum)
            count++;
        }
        if(root.left != null)
            count = pathSum(root.left, sum, count, arr);
        if(root.right != null)
            count = pathSum(root.right, sum, count, arr);
        arr.remove(arr.size()-1);
        return count;
    }

  static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int v) {
      this.val = v;
    }
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(10);
    root.left = new TreeNode(5);
    root.right = new TreeNode(-3);
    root.left.left = new TreeNode(3);
    root.left.right = new TreeNode(2);
    root.right.right = new TreeNode(11);
    root.left.left.left = new TreeNode(3);
    root.left.left.right = new TreeNode(-2);
    root.left.right.right = new TreeNode(1);
    System.out.println(pathSum(root, 8));
  }
}

The idea is to populate an aarray with the value along the path as you traverse the tree recursively, making sure you remove elements as you return. When you visit a node, you have to consider all the sums from that node to any node on the path to the root. Any of them can add up to your reference value. This implementation is O(nlogn), as you traverse n nodes, and for each you traverse an array of len up to log(n).