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))