题目链接：427. 建立四叉树
题目给定的 $n \times n$ 矩阵的大小 $n = 2^x$，因此这个矩阵的每一层次都可以通过平均分为四个大小为 $n’ = 2^{x - 1}$ 的矩阵获得。递归建立四叉树即可。
"""
Definition for a QuadTree node.
"""
from itertools import pairwise, chain
from typing import List
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
m = len(grid)
assert m > 0
n = len(grid[0])
assert n > 0
assert m == n
def _construct(t: int, b: int, l: int, r: int):
if t == b and l == r:
return Node(grid[t][l], True, None, None, None, None)
if all(a == b for a, b in pairwise(chain(*(row[l: r + 1] for row in grid[t: b + 1])))):
return Node(grid[t][l], True, None, None, None, None)
vm, hm = (t + b + 1) // 2, (l + r + 1) // 2
return Node(
False, False,
_construct(t, vm - 1, l, hm - 1),
_construct(t, vm - 1, hm, r),
_construct(vm, b, l, hm - 1),
_construct(vm, b, hm, r),
)
return _construct(0, n - 1, 0, n - 1)
obj = Solution().construct([[0, 1], [1, 0]])