Given a binary tree in which each node contains an integer number. Determine if there exists a path(the path can only be from one node to itself or to any of its descendants),the sum of the numbers on the path is the given target number.

Examples

5

/ \

2 11

 /    \

6     14

/

3

If target = 17, There exists a path 11 + 6, the sum of the path is target.

If target = 20, There exists a path 11 + 6 + 3, the sum of the path is target.

If target = 10, There does not exist any paths sum of which is target.

If target = 11, There exists a path only containing the node 11.

Solution: 路径只能从上到下，类似利用preSum和hashset找和为target的subarray

  boolean flag = false;
  public boolean exist(TreeNode root, int target) {
    if (root == null) {
      return flag;
    }
    Set<Integer> hashset = new HashSet<>();
    hashset.add(0);
    helper(root, 0, target, hashset);
    return flag;
  }
  private void helper(TreeNode root, int preSum, int target, Set<Integer> hashset) {
  //已找到就不需要再找
    if (flag) {
      return;
    }
    int sum = preSum + root.key;
    if (hashset.contains(sum - target)) {
      flag = true;
      return;
    }
    //true if the hashset didn't have the sum before
    boolean needRemove = hashset.add(sum);
    if (root.left != null) {
      helper(root.left, sum, target, hashset);
    }
    if (root.right != null) {
      helper(root.right, sum, target, hashset);
    }
    //不能直接hashset remove，只有是这层加入hashset的可以remove
    if (needRemove) {
      hashset.remove(sum);
    }
  }

或者用arraylist逐个检查：

Follow up 1: 若要找个数，则用hashmap:

    int count = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return count;
        }
        Map<Integer, Integer> hashmap = new HashMap<>();
        hashmap.put(0, 1);
        helper(root, 0, sum, hashmap);
        return count;
    }
    private void helper(TreeNode root, int preSum, int target, Map<Integer, Integer> hashmap) {

        int sum = preSum + root.val;
        if (hashmap.containsKey(sum - target)) {
            count += hashmap.get(sum - target);
        }

        hashmap.put(sum, hashmap.getOrDefault(sum, 0) + 1);

        if (root.left != null) {
            helper(root.left, sum, target, hashmap);
        }
        if (root.right != null) {
            helper(root.right, sum, target, hashmap);
        }
        hashmap.put(sum, hashmap.get(sum) - 1);

    }

Follow up 2: 找出所有路径：

Solution 1: 把node.val放入path list，对每个node，看当前path的元素有没有和为target (从尾开始看)

    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null){
            return res;
        }
        List<Integer> path = new ArrayList<Integer>();
        path.add(root.val);
        helper(root, target, path, res);
        return res;
    }
    private void helper(TreeNode root, int target, List<Integer> path, List<List<Integer>> res){

        if(root == null){
            return;
        }
        int sum = 0;
        //从尾开始加
        for(int i = path.size() - 1; i >= 0; i--){
            sum += path.get(i);
            if(sum == target) {
                List<Integer> temp = new ArrayList<Integer>();
                for(int j = i; j < path.size(); j++){
                    temp.add(path.get(j));
                }
                res.add(temp);
            }
        }
        if(root.left != null){
            path.add(root.left.val);
            helper(root.left, target, path, res);
            path.remove(path.size() - 1);
        }
        if(root.right != null){
            path.add(root.right.val);
            helper(root.right, target, path, res);
            path.remove(path.size() - 1);
        }
    }

Solution 2: 把path加入各preSum，同时把preSum和对应的index存到hashmap

    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null){
            return res;
        }
        List<Integer> path = new ArrayList<Integer>();
        Map<Integer, List<Integer>> hashmap = new HashMap<>();
        List<Integer> temp = new ArrayList<Integer>();
        temp.add(0);
        hashmap.put(0, temp);    
        helper(root, 0, target, hashmap, 1, path, res);
        return res;
    }
    private void helper(TreeNode root, int preSum, int target, Map<Integer, List<Integer>> hashmap, int index, List<Integer> path, List<List<Integer>> ans) {

        int sum = preSum + root.val;
        if (hashmap.containsKey(sum - target)) {
            List<Integer> list = hashmap.get(sum - target);
            for (int start : list) {
                List<Integer> temp = new ArrayList<Integer>();
                for (int i = start; i < path.size(); i++) {
                    if (i == 0) {
                        temp.add(path.get(i));
                    } else {
                    //注意存的是preSum，所以要相减得到元素值
                        temp.add(path.get(i) - path.get(i - 1));
                    }
                }
                temp.add(root.val);
                ans.add(temp);
            }

        }

        if (!hashmap.containsKey(sum)) {
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(index);
            hashmap.put(sum, temp);
        } else {
            hashmap.get(sum).add(index);           
        }

        path.add(sum);

        if (root.left != null) {
            helper(root.left, sum, target, hashmap, index + 1, path, ans);
        }
        if (root.right != null) {
            helper(root.right, sum, target, hashmap, index + 1, path, ans);
        }

        //记得清除hashmap和path
        List<Integer> temp = hashmap.get(sum);
        if (temp.size() == 1) {
            hashmap.remove(sum);
        } else {
            temp.remove(temp.size() - 1);
        }
        path.remove(path.size() - 1);
     }