⚡Flashcard Drill➔
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

  1. Recursively examine the region (r, c) of size size.
  2. If every cell in the region has the same value, return a leaf with that value.
  3. Otherwise split into four quadrants of size size / 2 and recurse, in the order top-left, top-right, bottom-left, bottom-right.
  4. 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 val on internal nodes: val is only meaningful for leaves; the constructor's isLeaf flag governs.
  • Forgetting the size == 1 case: 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems