Root-to-leaf equals target

boolean hasPathSum(Node n, int target) {
  if (n == null) return false;
  if (n.left == null && n.right == null) return n.val == target;
  return hasPathSum(n.left, target - n.val) || hasPathSum(n.right, target - n.val);
}
Advertisement

All root-to-leaf paths with sum

void allPaths(Node n, int target, List cur, List> result) {
  if (n == null) return;
  cur.add(n.val);
  if (n.left == null && n.right == null && target == n.val) result.add(new ArrayList<>(cur));
  allPaths(n.left, target - n.val, cur, result);
  allPaths(n.right, target - n.val, cur, result);
  cur.remove(cur.size() - 1);
}
Advertisement

Count paths (any→any) with sum

Prefix-sum HashMap. At each node, look for prefixSum - target in the map. Update map before recursing, remove after (backtrack).

Max path sum (any→any)

int maxSum = Integer.MIN_VALUE;
int gain(Node n) {
  if (n == null) return 0;
  int l = Math.max(0, gain(n.left));
  int r = Math.max(0, gain(n.right));
  maxSum = Math.max(maxSum, l + r + n.val);
  return n.val + Math.max(l, r);
}