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.

How is the binary tree represented?

We use the level order traversal sequence with a special symbol "#" denoting the null node.

For Example:

The sequence [1, 2, 3, #, #, 4] represents the following binary tree:

1

/ \

2 3

  /

4

/**

* public class TreeNode {

* public int key;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int key) {

* this.key = key;

* }

* }

*/

// O(n)

// use hashSet store the prefix sum, if the current prefixSum - target is already in the prefixSum hashSet, which meaning path //found. Since HashSet is not order data structure, so need to store the prefix sum at the current traveling root.

// another pitfall is before add current prefix sum to HashSet, need to check whether already contains the same number. if //contains, can't remove this number after traveling the left and right subtree. Because of the hashSet can't contain duplicate //number.

public class Solution {

public boolean exist(TreeNode root, int target) {

public class Solution {
  public boolean exist(TreeNode root, int target) {
    // Write your solution here.

    if (root == null) {

      return false;

    }

    Set<Integer> prefixSum = new HashSet<Integer>();

    prefixSum.add(0);

    int prevSum = 0;

    return helper(root,target,prefixSum,prevSum);
  }

   // from top to bottom
  // prevSum store the prefix sum up to the current root node
  private boolean helper(TreeNode root, int target, Set<Integer> prefixSum, int prevSum) {

    prevSum += root.key;

    if (prefixSum.contains(prevSum - target)) {

      return true;
    }

    boolean needRemove = prefixSum.add(prevSum);

    if (root.left != null && helper(root.left,target,prefixSum,prevSum)) {

      return true;

    }



    if (root.right != null && helper(root.right, target, prefixSum,prevSum)) {

      return true;

    }



    if (needRemove) {

      prefixSum.remove(prevSum);

    }

    return false;
  }
}