NeetCode #435LC-427MediumTreesNC 250
← Back to All Problems#435 · #427 · Construct Quad Tree(建立四叉树)
📌 Problem Statement & Constraints
Given an
n x n binary matrix grid with n a power of two, construct a quad tree where each node has isLeaf, val (only meaningful for leaves) and four children in the order top-left, top-right, bottom-left, bottom-right. A node is a leaf when all values in its region are identical. Constraints: n == grid.length == grid[i].length, n is a power of two, n <= 64.💡 Core Algorithmic Approaches
- Recursively examine the region
(r, c)of sizesize. - If every cell in the region has the same value, return a leaf with that value.
- Otherwise split into four quadrants of size
size / 2and recurse, in the order top-left, top-right, bottom-left, bottom-right. - The base case is
size == 1, which is always a leaf.
💻 Benchmark Python3 Implementation
class Solution:
def construct(self, grid: List[List[int]]) -> "Node":
def build(r: int, c: int, size: int) -> "Node":
first = grid[r][c]
uniform = True
for i in range(r, r + size):
for j in range(c, c + size):
if grid[i][j] != first:
uniform = False
break
if not uniform:
break
if uniform:
return Node(first == 1, True) # leaf
half = size // 2
return Node(True, False,
build(r, c, half), # top-left
build(r, c + half, half), # top-right
build(r + half, c, half), # bottom-left
build(r + half, c + half, half)) # bottom-right
return build(0, 0, len(grid))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 log n) in the worst case: each level of the recursion scans the whole grid, and there are log n levels. A per-region sum optimisation reduces the scanning.
💾 Space Complexity
O(log n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Getting the child order wrong: the required order is top-left, top-right, bottom-left, bottom-right.
- Setting
valon internal nodes:valis only meaningful for leaves; the constructor'sisLeafflag governs. - Forgetting the
size == 1case: it is covered by the uniformity scan, which always succeeds for a single cell. - Using a cumulative sum to avoid rescanning: a valid optimisation, but the straightforward scan is clearer and fast enough for n <= 64.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.