Mdhornet90
BAN USERMinor variation of another answer already listed. In Java:
void printSpiral(Node root) {
final int height = getHeight(root);
int i;
for (i = 0; i < (height / 2); i++) {
printLevelLeftToRight(i + 1, 1, root);
printLevelRightToLeft(height - i, 1, root);
}
if ((height % 2) == 1) {
printLevelLeftToRight(i + 1, 1, root);
}
System.out.println();
}
void printLevelLeftToRight(final int desiredLevel, int currentLevel, final Node node) {
if (desiredLevel == currentLevel) {
System.out.print(node.data + " ");
return;
}
if (node.left != null) {
printLevelLeftToRight(desiredLevel, currentLevel + 1, node.left);
}
if (node.right != null) {
printLevelLeftToRight(desiredLevel, currentLevel + 1, node.right);
}
}
void printLevelRightToLeft(final int desiredLevel, int currentLevel, final Node node) {
if (desiredLevel == currentLevel) {
System.out.print(node.data + " ");
return;
}
if (node.right != null) {
printLevelRightToLeft(desiredLevel, currentLevel + 1, node.right);
}
if (node.left != null) {
printLevelRightToLeft(desiredLevel, currentLevel + 1, node.left);
}
}
Two examples. First time through I misread the prompt and thought they only wanted N, so I derived a summation formula based on looking up the i^2 one. I then realized it was asking for the whole series, so an alternative that uses an accumulator is listed as well. Both run in O(n) and use O(1) space, and the alternate might end up being a hair faster due to fewer mathematical operations.
int[] computeUpToNInSeries(int n) {
final int[] series = new int[n];
for (int i = 1; i <= n; i++) {
series[i - 1] = compute(i);
}
return series;
}
int compute(int i) {
return (i * (i - 1) * (2*i - 1)) / 6 + 1;
}
int[] alternateComputeUpToNInSeries(int n) {
final int[] series = new int[n];
int accumulator = 1;
for (int i = 1; i <= n; i++) {
series[i - 1] = accumulator;
accumulator += i * i;
}
return series;
}
A variation of level-order traversal. Because something can only be a neighbor when it's on the same level, it means we should keep the current level and the next level separated. And because a Node only has knowledge of its immediate child, that means we really only need to know about two levels at any time. This algorithm runs in O(n) time, using O(n) space.
- Mdhornet90 December 13, 2015