Nilaksh Bajpai
BAN USERpublic class RotateSquareMatrix {
private static final int hi = 2;
private static final int lo = 0;
private int[][] matrix = new int[3][3];
{
matrix[0][0] = 1;
matrix[0][1] = 2;
matrix[0][2] = 3;
matrix[1][0] = 4;
matrix[1][1] = 5;
matrix[1][2] = 6;
matrix[2][0] = 7;
matrix[2][1] = 8;
matrix[2][2] = 9;
}
public static void main(String[] args) {
RotateSquareMatrix sq = new RotateSquareMatrix();
System.out.println("Input:");
print(sq);
int i = 0, j = 0;
Direction d = Direction.right;
int val = sq.matrix[i][j];
while (d != Direction.stop) {
d = sq.findDirection(i, j, d);
switch (d) {
case left:
j--;
break;
case right:
j++;
break;
case top:
i--;
break;
case bottom:
i++;
break;
}
if (d != Direction.stop){
int temp = sq.matrix[i][j];
sq.matrix[i][j] = val;
val = temp;
}
}
System.out.println();
System.out.println("Output:");
print(sq);
}
static void print(RotateSquareMatrix sq) {
for (int k = 0; k < sq.matrix.length; k++) {
System.out.print(sq.matrix[k][0]);
System.out.print(" "+sq.matrix[k][1]);
System.out.println(" "+sq.matrix[k][2]);
}
}
private Direction findDirection(int i, int j, Direction curr) {
Direction d = curr;
if (curr == Direction.right && j == hi) {
d = Direction.bottom;
} else if (curr == Direction.bottom && i == hi) {
d = Direction.left;
} else if (curr == Direction.left && j == lo) {
d = Direction.top;
} else if (curr == Direction.top && i == lo) {
d = Direction.stop;
}
return d;
}
enum Direction {
left, right, top, bottom, stop
}
}
Input:
1 2 3
4 5 6
7 8 9
Output:
4 1 2
7 5 3
8 9 6
Something like the following could help. I did a level order recursive traversal and introduced a variable for direction.
public static void main(String[] args) {
ZigZagBT bt = new ZigZagBT();
Node root = bt.createBT();
int height = bt.getHeight(root, 0);
boolean ltr = false;
for (int i = 1; i <= height; i++) {
bt.traverse(root, i, ltr);
System.out.println();
ltr = !ltr;
}
}
private void traverse(Node node, int level, boolean ltr) {
if (node == null)
return;
if (level == 1) {
System.out.print(node.id);
} else if (level > 1) {
if (ltr) {
if (node.left != null) {
traverse(node.left, level - 1, ltr);
}
if (node.right != null) {
traverse(node.right, level - 1, ltr);
}
}else{
if (node.right != null) {
traverse(node.right, level - 1, ltr);
}
if (node.left != null) {
traverse(node.left, level - 1, ltr);
}
}
}
}
If distances can be taken as 32bit integers (say in light years) then LSD Radix sort (maybe with a first pass of MSD Radix Sort) could be a good way to go about things unless memory is also a constraint. In that case external merge sort should be fine.
- Nilaksh Bajpai May 23, 2015