Leetcode 772 Solution

This article provides solution to leetcode question 772 (construct-quad-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 772" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/construct-quad-tree

Solution

"""
# Definition for a QuadTree node.
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':
        n = len(grid)

        def _construct(i1, j1, i2, j2):
            nonlocal grid

            all_same = True
            val = None
            for i in range(i1, i2):
                for j in range(j1, j2):
                    if val is None:
                        val = grid[i][j]
                    else:
                        if val != grid[i][j]:
                            all_same = False
                            break
                if not all_same:
                    break

            if all_same:
                return Node(val, all_same, None, None, None, None)
            else:
                mid_i = (i1 + i2) // 2
                mid_j = (j1 + j2) // 2

                return Node(
                    False,
                    False,
                    _construct(i1, j1, mid_i, mid_j),
                    _construct(i1, mid_j, mid_i, j2),
                    _construct(mid_i, j1, i2, mid_j),
                    _construct(mid_i, mid_j, i2, j2),
                )

        return _construct(0, 0, n, n)