基于一个值为0或1的方阵构建Quad Tree，DFS
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))