Monday, August 8, 2016

[Solution]

class TNode {
public char val;

public TNode leftTop;
public TNode rightTop;
public TNode leftBot;
public TNode rightBot;

public TNode(char val) {
this.val = val;
}
}

class Solution {

public TNode buildTree(char[][] image) {
int n = image.length;
return buildTree(image, 0, 0, n - 1, n - 1);
}

public TNode buildTree(char[][] image, int row1, int col1, int row2, int col2) {
if (row1 < 0 || row1 >= image.length || row2 < 0 || row2 >= image.length || col1 < 0 || col1 >= image.length || col2 < 0 || col2 >= image.length || row1 > row2 || col1 > col2) {
return null;
}

if (row1 == row2 && col1 == col2) {
TNode result = new TNode(image[row1][col1]);
if (image[row1][col1] == '1') {
result.val = '1';
}
else {
result.val = '0';
}
return result;
}

int midX = row1 + (row2 - row1) / 2;
int midY = col1 + (col2 - col1) / 2;

TNode root = new TNode('#');

TNode leftTop = buildTree(image, row1, col1, midX, midY);
TNode rightTop = buildTree(image, row1, midY + 1, midX, col2);
TNode leftBot = buildTree(image, midX + 1, col1, row2, midY);
TNode rightBot = buildTree(image, midX + 1, midY + 1, row2, col2);

if (leftTop.val == '1'
&& rightTop.val == '1'
&& leftBot.val == '1'
&& rightBot.val == '1') {

root.val = '1';
}
else if (leftTop.val == '0'
&& rightTop.val == '0'
&& leftBot.val == '0'
&& rightBot.val == '0') {

root.val = '0';
}
else {
root.leftTop = leftTop;
root.rightTop = rightTop;
root.leftBot = leftBot;
root.rightBot = rightBot;
}

return root;
}

public TNode imageAnd(TNode root1, TNode root2) {
TNode root = new TNode('#');
if (root1 == null && root2 == null) {
return null;
}
if (root1.val == '1' && root2.val == '1') {
return new TNode('1');
}
else if (root1.val == '0' || root2.val == '0') {
return new TNode('0');
}
else if (root1.val == '#' && root2.val == '1') {
root.leftTop = imageAnd(root1.leftTop, root2);
root.rightTop = imageAnd(root1.rightTop, root2);
root.leftBot = imageAnd(root1.leftBot, root2);
root.rightBot = imageAnd(root1.rightBot, root2);
}
else if (root1.val == '1' && root2.val == '#') {
root.leftTop = imageAnd(root1, root2.leftTop);
root.rightTop = imageAnd(root1, root2.rightTop);
root.leftBot = imageAnd(root1, root2.leftBot);
root.rightBot = imageAnd(root1, root2.rightBot);
}
else {
root.leftTop = imageAnd(root1.leftTop, root2.leftTop);
root.rightTop = imageAnd(root1.rightTop, root2.rightTop);
root.leftBot = imageAnd(root1.leftBot, root2.leftBot);
root.rightBot = imageAnd(root1.rightBot, root2.rightBot);
}
return root;
}

public void toMatrix(TNode root, char[][] matrix, int row1, int col1, int row2, int col2) {
if (root == null) {
return;
}

if (root.val == '1' || root.val == '0') {
for (int i = row1; i <= row2; i++) {
for (int j = col1; j <= col2; j++) {
matrix[i][j] = root.val;
}
}
}
else {
int midX = row1 + (row2 - row1) / 2;
int midY = col1 + (col2 - col1) / 2;
toMatrix(root.leftTop, matrix, row1, col1, midX, midY);
toMatrix(root.rightTop, matrix, row1, midY + 1, midX, col2);
toMatrix(root.leftBot, matrix, midX + 1, col1, row2, midY);
toMatrix(root.rightBot, matrix, midX + 1, midY + 1, row2, col2);
}
}
}