3.4 Path Sum to Target III

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.

Input: TreeNode root, int target

Output: boolean if such a path exists

Solution 1:

1. Top-down, carrying a prefixSum (using hashset) from root to current node

2. If the difference b/w two nodes == target, meaning the sum b/w these two nodes is target

3. curSum += node.key

curSum - target == starting of the path

Need to remove preSum before going back to previous layer

TC: n = # of nodes in the tree, only need to traverse once = O(n)

SC: new HashSet = O(n)

public boolean exist (TreeNode root, int target) {
  if (root == null) { return false; }
  Set<Integer> prefixSum = new HashSet<>();
  prefixSum.add(0);
  return helper(root, prefixSum, 0, target);
}

private boolean helper(TreeNode root, Set<Integer> prefixSum, int curSum, int target) {
  curSum += root.key;
  if (prefixSum.contains(curSum - target)) { return true; }
  boolean remove = prefixSum.add(curSum);
  if (root.left != null && helper(root.left, prefixSum, curSum, target)) {
    return true;
  }
  if (root.right != null && helper(root.right, prefixSum, curSum, target)) {
    return true;
  }
  if (remove) {
    prefixSum.remove(curSum);
  }
  return false;
}

Solution 2: Bottom-up

TC: worst case O(n^2), avg O(nlogn)

SC: O(height), worst O(n)

public boolean exist(TreeNode root, int target) {
  if (root == null) { return false; }
  return helper(root, target) || exist(root.left, target) || exist(root.right, target);
}

 private boolean helper(TreeNode root, int target) {
  if (root == null) { return false; }
  return root.key == target || helper(root.left, target - root.key) 
|| helper(root.right, target - root.key);
}