1 #427
 2 #Runtime: 100 ms (Beats 98.35%)
 3 #Memory: 14.7 MB (Beats 86.50%)
 4 
 5 class Node:
 6     def __init__(self, val, isLeaf, topLeft = None, topRight = None, bottomLeft = None, bottomRight = None):
 7         self.val = val
 8         self.isLeaf = isLeaf
 9         self.topLeft = topLeft
10         self.topRight = topRight
11         self.bottomLeft = bottomLeft
12         self.bottomRight = bottomRight
13 
14 
15 class Solution:
16     def isLeaf(self, grid, x, y, w):
17         for i in range(x, x + w):
18             for j in range(y, y + w):
19                 if grid[x][y] != grid[i][j]:
20                     return False
21         return True
22 
23     def BuildTree(self, grid, x, y, w):
24         if self.isLeaf(grid, x, y, w):
25             return Node(grid[x][y] == 1, True)
26         r = Node(True, False)
27         r.topLeft = self.BuildTree(grid, x, y, w // 2)
28         r.topRight = self.BuildTree(grid, x, y + w // 2, w // 2)
29         r.bottomLeft = self.BuildTree(grid, x + w // 2, y, w // 2)
30         r.bottomRight = self.BuildTree(grid, x + w // 2, y + w // 2, w // 2)
31         return r
32 
33     def construct(self, grid: List[List[int]]) -> Node:
34         return self.BuildTree(grid, 0, 0, len(grid))