Medium
Quiz
#427 Construct Quad Tree
APPROACH
Given an n x n binary matrix grid, construct and return the root of its Quad-Tree.
Each node has two attributes:
- val: True for an all-1 region, False for an all-0 region (internal nodes may use either value).
- isLeaf: True when the region is uniform; False when it has four children.
Rule: if a region is uniform, make it a leaf; otherwise divide it into four equal quadrants and recurse into each.
Output is level-order with null sentinels; each node is serialized as [isLeaf, val] using 1 for True and 0 for False.
Example 1:
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
Example 2:
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represents False and 1 represents True in the photo representing the Quad-Tree.
Example 3:
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]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
1 of 4
1:00
What is the optimal approach for this problem?