Problem
Given a n * n
matrix grid
of 0's
and 1's
only. We want to represent the grid
with a Quad-Tree.
Return the root of the Quad-Tree representing the grid
.
Notice that you can assign the value of a node to True or False when isLeaf
is False, and both are accepted in the answer.
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 1’s or False if the node represents a grid of 0’s.isLeaf
: True if the node is leaf node on the tree or False if the node has the 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
1's
or all0's
) setisLeaf
True and setval
to the value of the grid and set the four children to Null and stop. - If the current grid has different values, set
isLeaf
to False and setval
to any value and divide the current grid into four sub-grids as shown in the photo. - Recurse for each of the children with the proper sub-grid.
If you want to know more about the Quad-Tree, you can refer to the wiki.
Quad-Tree format:
The output represents the serialized format of a Quad-Tree using level order traversal, where null
signifies a path terminator where no node exists below.
It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val]
.
If the value of isLeaf
or val
is True we represent it as 1 in the list [isLeaf, val]
and if the value of isLeaf
or val
is False we represent it as 0.
Examples
Example 1:
$$ \Huge \begin{array}{|c|c|} \hline \colorbox{orange} 0 & \colorbox{white} 1 \\ \hline \colorbox{Cerulean} 1 & \colorbox{green} 0 \\ \hline \end{array} $$
graph TD classDef orange fill:#FFA500,stroke:#333,stroke-width:2px; classDef white fill:#FFF,stroke:#333,stroke-width:2px; classDef blue fill:#00BFFF,stroke:#333,stroke-width:2px; classDef green fill:#32CD32,stroke:#333,stroke-width:2px; classDef root fill:#EEE,stroke:#333,stroke-width:2px; Root("Root
isLeaf:0
val:1") A("isLeaf:1
val:0") B("isLeaf:1
val:1") C("isLeaf:1
val:1") D("isLeaf:1
val:0") Root -- Top Left --> A Root -- Top Right --> B Root -- Bottom Left --> C Root -- Bottom Right --> D class A orange; class B white; class C blue; class D green; class Root root;
|
|
Example 2:
$$ \Huge \begin{array}{|c|c|c|c|c|c|c|c|} \hline \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{lightgray} 0 & \colorbox{lightgray} 0 \\ \hline \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{yellow} 0 & \colorbox{yellow} 0 & \colorbox{lightgray} 0 & \colorbox{lightgray} 0 \\ \hline \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{Thistle} 1 & \colorbox{Thistle} 1 & \colorbox{LimeGreen} 1 & \colorbox{LimeGreen} 1 \\ \hline \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{Thistle} 1 & \colorbox{Thistle} 1 & \colorbox{LimeGreen} 1 & \colorbox{LimeGreen} 1 \\ \hline \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 \\ \hline \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 \\ \hline \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 \\ \hline \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{Cerulean} 1 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 & \colorbox{lightgreen} 0 \\ \hline \end{array} $$
graph TD classDef orange fill:#FFA500,stroke:#333,stroke-width:2px; classDef blue fill:#00BFFF,stroke:#333,stroke-width:2px; classDef green fill:#32CD32,stroke:#333,stroke-width:2px; classDef root fill:#EEE,stroke:#333,stroke-width:2px; classDef yellow fill:#FFFF99,stroke:#333,stroke-width:2px; classDef lightgray fill:#D3D3D3,stroke:#333,stroke-width:2px; classDef lightpurple fill:#E6CCFF,stroke:#333,stroke-width:2px; classDef lightgreen fill:#90EE90,stroke:#333,stroke-width:2px; classDef white fill:#FFF,stroke:#333,stroke-width:2px; Root("Root
isLeaf:0
val:1") TL("isLeaf:1
val:1") TR("isLeaf:0
val:1") BL("isLeaf:1
val:1") BR("isLeaf:1
val:0") TR_TL("isLeaf:1
val:0") TR_TR("sLeaf:1
val:0") TR_BL("isLeaf:1
val:1") TR_BR("isLeaf:1
val:1") Root -- Top Left --> TL Root -- Top Right --> TR Root -- Bottom Left --> BL Root -- Bottom Right --> BR TR -- Top Left --> TR_TL TR -- Top Right --> TR_TR TR -- Bottom Left --> TR_BL TR -- Bottom Right --> TR_BR class Root root; class TL orange; class BL blue; class BR green; class TR white; class TR_TL yellow; class TR_TR lightgray; class TR_BL lightpurple; class TR_BR lightgreen;
|
|
Definition for a QuadTree Node
|
|
Solution
Method 1 – Recursive Divide and Conquer (Quad Tree Construction)
Intuition
The main idea is to recursively divide the grid
into four quadrants until each quadrant contains only a single value (all 0s or all 1s). At each step, we check if the current subgrid is uniform. If it is, we create a leaf node; otherwise, we continue dividing. This approach leverages the quad tree’s structure, where each node represents a region of the grid, and leaf nodes represent uniform regions.
Approach
- Define a recursive function that takes the current subgrid boundaries (
rowStart
,colStart
,rowEnd
,colEnd
). - Check if all values in the current subgrid are the same:
- If yes, return a leaf node with
isLeaf = true
andval
set to the value of the subgrid. - If not, divide the subgrid into four equal parts (top left, top right, bottom left, bottom right).
- If yes, return a leaf node with
- Recursively construct each of the four children using the corresponding subgrid boundaries.
- Return a non-leaf node with
isLeaf = false
and the four children attached. - Start the recursion with the entire grid.
Complexity
- ⏰ Time complexity:
O(n^2 log n)
in the worst case, as each level divides the grid and checks all cells in the region. - 🧺 Space complexity:
O(n^2)
for the tree structure and recursion stack.
Code
|
|
|
|
|
|
|
|
|
|
|
|
|
|