427. Construct Quad Tree - cocoder39/coco39_LC GitHub Wiki

427. Construct Quad Tree

Option 1: top-down + prefix sum

T = O(n^2)

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        n = len(grid)
        prefixSum = [[0] * n for i in range(n)]
        for i in range(n):
            sum_ = 0
            for j in range(n):
                sum_ += grid[i][j]
                prefixSum[i][j] = sum_
        
        for i in range(1, n):
            for j in range(n):
                prefixSum[i][j] += prefixSum[i-1][j]
        
        return self.helper(prefixSum, grid, 0, n-1, 0, n-1)
    
    def helper(self, prefixSum, grid, left, right, top, bottom) -> 'Node':
        #print(left, right, top, bottom)
        if left == right and top == bottom:
            return Node(grid[top][left], True, None, None, None, None)

        isLeaf = False
        total = prefixSum[bottom][right]
        if left >= 1:
            total -= prefixSum[bottom][left-1]
        if top >= 1:
            total -= prefixSum[top-1][right]
        if top >= 1 and left >= 1:
            total += prefixSum[top-1][left-1]
        
        if total == 0:
            isLeaf = True
            val = False
        elif total == (bottom+1-top) * (right+1-left):
            isLeaf = True
            val = True
        
        if isLeaf:
            return Node(val, True, None, None, None, None)
        
        hm = (right+left)//2
        vm = (bottom+top)//2
        topLeft = self.helper(prefixSum, grid, left, hm, top, vm)
        topRight = self.helper(prefixSum, grid, hm+1, right, top, vm)
        bottomLeft = self.helper(prefixSum, grid, left, hm, vm+1, bottom)
        bottomRight = self.helper(prefixSum, grid, hm+1, right, vm+1, bottom)
        return Node(True, False, topLeft, topRight, bottomLeft, bottomRight)

Option 2: bottom up

T = O(n^2)

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        n = len(grid)    
        return self.helper(grid, 0, n-1, 0, n-1)
    
    def helper(self, grid, left, right, top, bottom) -> 'Node':
        #print(left, right, top, bottom)
        if left == right and top == bottom:
            return Node(grid[top][left], True, None, None, None, None)
        
        hm = (right+left)//2
        vm = (bottom+top)//2
        topLeft = self.helper(grid, left, hm, top, vm)
        topRight = self.helper(grid, hm+1, right, top, vm)
        bottomLeft = self.helper(grid, left, hm, vm+1, bottom)
        bottomRight = self.helper(grid, hm+1, right, vm+1, bottom)
        
        if topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and topLeft.val == topRight.val == bottomLeft.val == bottomRight.val:
            return Node(topLeft.val, True, None, None, None, None)
        
        return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)