Ankur Sharma
BAN USER@m No. Only assuming they both are Binary Trees. In the above example, tree1 has 3 nodes while tree2 has 6
- Ankur Sharma February 23, 2014well..copy paste the code and run it yourself
- Ankur Sharma February 23, 201450
10
100
15
150
175
20
200
250
Recurse the two trees simultaneously. Essentially, we are printing the nodes at the same level and side in the two trees. It can be easily extended to sum (or any operation on) the corresponding nodes of the two trees.
public class InOrder2Trees {
static class Node {
private int data;
private Node leftChild;
private Node rightChild;
public Node(int data) {
this.data = data;
}
public void leftChild(int data) {
this.leftChild = new Node(data);
}
public void rightChild(int data) {
this.rightChild = new Node(data);
}
}
public static void main(String[] args) {
Node root1 = new Node(15);
root1.leftChild(10);
root1.rightChild(20);
Node root2 = new Node(150);
root2.leftChild(100);
root2.rightChild(200);
root2.leftChild.leftChild(50);
root2.rightChild.leftChild(175);
root2.rightChild.rightChild(250);
printInorder(root1, root2);
}
private static void printInorder(Node root1, Node root2) {
if (root1 == null && root2 == null)
return;
Node r1l = root1 == null ? null : root1.leftChild;
Node r2l = root2 == null ? null : root2.leftChild;
printInorder(r1l, r2l);
if (root1 != null)
System.out.println(root1.data);
if (root2 != null)
System.out.println(root2.data);
Node r1r = root1 == null ? null : root1.rightChild;
Node r2r = root2 == null ? null : root2.rightChild;
printInorder(r1r, r2r);
}
}
package misc;
public class MatrixFill {
static int N = 10;
static int M = 11;
static int order = 0;
static char[][] matrix = new char[N][M];
public static void main(String[] args) {
matrix[0] = "XXXXXXXXXXX".toCharArray();
matrix[1] = "XXXXOOXXXXX".toCharArray();
matrix[2] = "XXXXXXXXXXX".toCharArray();
matrix[3] = "XOXXXXOOOXX".toCharArray();
matrix[4] = "XOOOXXXXOXX".toCharArray();
matrix[5] = "XXXOXXXXOXX".toCharArray();
matrix[6] = "XOOOXXOOOXX".toCharArray();
matrix[7] = "XOXXXXXXXXX".toCharArray();
matrix[8] = "XOOOOOOOOOO".toCharArray();
matrix[9] = "XXXXXXXXXXX".toCharArray();
printMatrix();
substitute('O');
compute();
substitute('1', 'X');
substitute('0', 'O');
printMatrix();
}
private static void printMatrix() {
System.out.println(order);
for (int i = 0; i < N; i++) {
System.out.println(String.valueOf(matrix[i], 0, M));
}
System.out.println();
}
private static void compute() {
boolean changed = true;
while (changed) {
printMatrix();
order++;
changed = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] != 'X') {
changed = computeCell(i, j) || changed;
}
}
}
}
}
private static boolean computeCell(int i, int j) {
char value = matrix[i][j];
int x, y;
for (x = i, y = j; y < M && matrix[x][y] != 'X'; y++) {
multiply(i, j, x, y);
}
for (x = i, y = j; y > 0 && matrix[x][y] != 'X'; y--) {
multiply(i, j, x, y);
}
for (x = i, y = j; x < N && matrix[x][y] != 'X'; x++) {
multiply(i, j, x, y);
}
for (x = i, y = j; x > 0 && matrix[x][y] != 'X'; x--) {
multiply(i, j, x, y);
}
return value != matrix[i][j];
}
private static void multiply(int i, int j, int x, int y) {
if (matrix[x][y] != 'X') {
matrix[i][j] = matrix[x][y] == '0' ? '0' : matrix[i][j];
matrix[x][y] = matrix[i][j] == '0' ? '0' : matrix[x][y];
}
}
private static void substitute(char c) {
order++;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == c) {
if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
matrix[i][j] = '0';
} else {
matrix[i][j] = '1';
}
}
}
}
}
private static void substitute(char c, char d) {
order++;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == c)
matrix[i][j] = d;
}
}
}
}
this has few N/M typos
posting a better algo below
public class MatrixFill {
static int N = 10;
static int M = 11;
static int order = 0;
static char[][] matrix = new char[N][M];
public static void main(String[] args) {
matrix[0] = "XXXXXXXXXXX".toCharArray();
matrix[1] = "XXXXOOXXXXX".toCharArray();
matrix[2] = "XXXXOOXXXXX".toCharArray();
matrix[3] = "XXXXXXXXXXX".toCharArray();
matrix[4] = "XXXXXXOXXXX".toCharArray();
matrix[5] = "XXXXXXOXXXX".toCharArray();
matrix[6] = "XXXXXXOXXXX".toCharArray();
matrix[7] = "XXXXXXOXXXX".toCharArray();
matrix[8] = "XXXXXXOOOOO".toCharArray();
matrix[9] = "XXXXXXXXXXX".toCharArray();
printMatrix();
substitute('O');
compute();
substitute('1', 'X');
substitute('0', 'O');
printMatrix();
}
private static void printMatrix() {
System.out.println(order);
for (int i = 0; i < N; i++) {
System.out.println(String.valueOf(matrix[i], 0, M));
}
System.out.println();
}
private static void compute() {
boolean changed = true;
while (changed) {
printMatrix();
order++;
changed = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] != 'X') {
changed = computeCell(i, j) || changed;
}
}
}
}
}
private static boolean computeCell(int i, int j) {
char value = matrix[i][j];
if (j > 0) {
matrix[i][j] = multiply(i, j, i, j - 1);
}
if (i > 0) {
matrix[i][j] = multiply(i, j, i - 1, j);
}
if (j < N - 1) {
matrix[i][j] = multiply(i, j, i, j + 1);
}
if (i < N - 1) {
matrix[i][j] = multiply(i, j, i + 1, j);
}
return value != matrix[i][j];
}
private static char multiply(int i, int j, int x, int y) {
if (matrix[x][y] == 'X')
return matrix[i][j];
return matrix[x][y] == '0' ? '0' : matrix[i][j];
}
private static void substitute(char c) {
order++;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (matrix[i][j] == c) {
if (i == 0 || i == N - 1 || j == 0 || j == N - 1) {
matrix[i][j] = '0';
} else {
matrix[i][j] = '1';
}
}
}
}
}
private static void substitute(char c, char d) {
order++;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == c)
matrix[i][j] = d;
}
}
}
}
@m Yes. That's by design. Since the question was unclear on what to do when the trees have different structures, I assumed that we are supposed to print the corresponding nodes alternatively. If you put 10, 15, 20 and 100, 150, 200 in my code, you shall get the same result as mentioned in the question.
- Ankur Sharma February 23, 2014Thus, if the two trees have n and m nodes, we will recurse in O (max(n,m) * log (max(n,m)))