Construct Quad Tree
Intuition
Solution
class Solution:
def _construct_helper(self, grid, rlo, clo, rhi, chi):
if rhi - rlo == 1:
return Node(grid[rlo][clo] == 1, True, None, None, None, None)
rdiv = (rlo + rhi) // 2
cdiv = (clo + chi) // 2
corners = [
self._construct_helper(grid, rlo, clo, rdiv, cdiv),
self._construct_helper(grid, rlo, cdiv, rdiv, chi),
self._construct_helper(grid, rdiv, clo, rhi, cdiv),
self._construct_helper(grid, rdiv, cdiv, rhi, chi),
]
if len(set([corner.val for corner in corners])) == 1 and \
False not in [corner.isLeaf for corner in corners]:
return Node(grid[rlo][clo] == 1, True, None, None, None, None)
else:
return Node(
True, False,
corners[0], corners[1], corners[2], corners[3]
)
def construct(self, grid: List[List[int]]) -> 'Node':
if not grid:
return None
return self._construct_helper(grid, 0, 0, len(grid), len(grid))