Construct Quad Tree

Problem

Given a n * n matrix grid of 0s and 1s only. We want to represent grid with a Quad-Tree.

Return the root of the Quad-Tree representing grid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

val: True if the node represents a grid of 1s or False if the node represents a grid of 0s. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
isLeaf: True if the node is a leaf node on the tree or False if the node has four children.

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e., all 1s or all 0s), set isLeaf to True and set val to the value of the grid and set the four children to None and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids.
Recurse for each of the children with the proper sub-grid.

Examples

Input: grid = [[0,1],[1,0]]

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

The grid has mixed values, so we create an internal node with four leaf children. Each quadrant contains a single cell, so each becomes a leaf node with its respective value.

Input:

grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]

Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

The grid is divided into four quadrants. The top-left, bottom-left, and bottom-right quadrants each have uniform values and become leaf nodes. The top-right quadrant has mixed values, so it is further subdivided into four leaf nodes.

Construct Quad Tree

Problem

Constraints

Examples