Medium

Construct Quad Tree

LAB

Given a binary grid, return the preorder encoding of its compressed quad tree using 1 for leaf nodes and 0 for internal nodes.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      0,
      1
    ],
    [
      1,
      0
    ]
  ]
}

Output
[
  0,
  1,
  0,
  1,
  1,
  1,
  1,
  1,
  0
]

FUNCTION SHAPE

grid: intMatrix→intArray

SOLUTION NOTE

This is a common problem in your first algorithms course. We construct a recursive build quad tree function with (i,j) coordinates of the top left corner of the square we are building the quad tree over, with (i+length, j+length) as the bottom right corner. The base case is when the square is size 1, this is a leaf node. Otherwise we recursively build the 4 sub quadrant squares.

Now, when is this current node a leaf? When all 4 sub quadrants are leaves, and they all have the same value! Otherwise, this node is an interior node with corresponding sub quad trees.

This is T(n) = 4*T(n/4) + O(1) time = O(n) time.

Reveal reference solution +

pythonREFERENCE

"""
class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None,
                 bottomLeft=None, bottomRight=None):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid):
        return self.recurse(grid, 0, 0, len(grid))

    def recurse(self, grid, i, j, length):
        if length == 1:
            return Node(grid[i][j], True)

        half = length // 2
        topLeft = self.recurse(grid, i, j, half)
        topRight = self.recurse(grid, i, j + half, half)
        bottomLeft = self.recurse(grid, i + half, j, half)
        bottomRight = self.recurse(grid, i + half, j + half, half)

        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)
        else:
            return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗