Algorithms/ConstructQuadTree.java at master · manjeersrujan/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
 * https://leetcode.com/problems/construct-quad-tree/
 */

// Definition for a QuadTree node.
class Node {
	public boolean val;
	public boolean isLeaf;
	public Node topLeft;
	public Node topRight;
	public Node bottomLeft;
	public Node bottomRight;

	public Node() {
	}

	public Node(boolean _val, boolean _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight) {
		val = _val;
		isLeaf = _isLeaf;
		topLeft = _topLeft;
		topRight = _topRight;
		bottomLeft = _bottomLeft;
		bottomRight = _bottomRight;
	}
};

class ConstructQuadTree {
	public Node construct(int[][] grid) {
		return construct(grid, 0, 0, grid.length - 1, grid.length - 1);
	}

	private Node construct(int[][] grid, int i, int j, int k, int l) {

		if (i == k && j == l) {
			return new Node(grid[i][j] == 1 ? true : false, true, null, null, null, null);
		}
		if (checkIfSame(grid, i, j, k, l) == 1) {
			return new Node(true, true, null, null, null, null);
		} else if (checkIfSame(grid, i, j, k, l) == 0) {
			return new Node(false, true, null, null, null, null);
		} else {
			Node lT = construct(grid, i, j, (i + k) / 2, (j + l) / 2);
			Node lB = construct(grid, ((i + k) / 2) + 1, j, k, (j + l) / 2);
			Node rT = construct(grid, i, ((j + l) / 2) + 1, (i + k) / 2, l);
			Node rB = construct(grid, ((i + k) / 2) + 1, ((j + l) / 2) + 1, k, l);
			return new Node(true, false, lT, rT, lB, rB);
		}
	}

	/**
	 * @param grid
	 * @param leftTop
	 * @param rightBottom
	 * @return
	 *
	 * 		1 -> all 1 0 -> all 0 -1 -> not uniform
	 */
	private int checkIfSame(int[][] grid, int leftTopX, int leftTopY, int rightBottomX, int rightBottomY) {

		int val = grid[leftTopX][leftTopY];
		for (int i = leftTopX; i <= rightBottomX; i++) {
			for (int j = leftTopY; j <= rightBottomY; j++) {
				if (grid[i][j] != val) {
					return -1;
				}
			}
		}
		return val;
	}
}