dph
BAN USERAnother simple Java solution similar to some of the C++ ones. We could avoid having 2 additional fields by extracting them into a value type that can be returned.
private static Node<Integer> head;
private static Node<Integer> tail;
private static void flattenRecursive(Node<Integer> n) {
if (n == null) {
return;
} else {
flattenRecursive(n.left);
if (head == null) {
head = n;
tail = head;
} else {
tail.right = n;
n.left = tail;
tail = n;
}
flattenRecursive(n.right);
}
// Could make the list circular here
}
Another Java version using a loop:
private static boolean sumLoop(int[] arr, int target) {
for (int sum = 0, i = 0, j = 0;;) {
if (sum == target) {
return true;
}
if (sum < target && i < arr.length) {
sum += arr[i++];
} else if (sum > target && j < arr.length) {
sum -= arr[j++];
} else {
return false;
}
}
}
Do you mind sharing that solution then? Using a 2-pointer approach I can get the min OR max for any sequence in O(n) time with O(1) additional space usage. Not sure how you would do that in constant time.
- dph April 07, 2015