Practice/Uber/Leetcode 427. Construct Quad Tree

Leetcode 427. Construct Quad Tree

CodingOptional

Problem

You are given an n × n binary matrix where n is a power of 2 (the matrix contains only 0s and 1s). Your task is to build a quadtree representation of this matrix.

A quadtree is a tree data structure where each internal node has exactly four children. For this problem, each node represents a rectangular region of the matrix and has the following properties:

• val: A boolean representing the value of the region (true for 1, false for 0). Only meaningful for leaf nodes.
• isLeaf: A boolean indicating whether the node is a leaf (true) or internal node (false).
• topLeft, topRight, bottomLeft, bottomRight: Four child nodes representing the four quadrants.

The construction follows these rules:

1. If the current region contains all the same value (all 0s or all 1s), create a leaf node with isLeaf = true and val equal to that value.
2. If the current region contains mixed values, create an internal node with isLeaf = false, then recursively divide the region into four equal quadrants and build the tree for each quadrant.

The quadrants are divided in this order: top-left, top-right, bottom-left, bottom-right.

Requirements

1. Implement a function that takes a square binary matrix as input
2. Return the root node of the constructed quadtree
3. Use recursive divide-and-conquer to build the tree
4. Handle regions of varying sizes from n×n down to 1×1
5. Properly identify uniform regions to create leaf nodes

Constraints

• n == grid.length == grid[i].length
• n is a power of 2 (1, 2, 4, 8, 16, ...)
• 1 ≤ n ≤ 64
• grid[i][j] is either 0 or 1
• Time complexity: O(n² log n) in worst case
• Space complexity: O(log n) for recursion stack

Examples

Example 1:

Input: grid = [[1,1],[1,1]] Output: Node(isLeaf=True, val=True) Explanation: The entire 2×2 grid contains only 1s, so we return a single leaf node with value true.

Example 2:

Input: grid = [[0]] Output: Node(isLeaf=True, val=False) Explanation: A 1×1 grid is always a leaf node. Since the cell is 0, val is false.

Example 3:

Input: grid = [[1,0],[0,1]] Output: Node(isLeaf=False, val=True, topLeft=Node(isLeaf=True, val=True), topRight=Node(isLeaf=True, val=False), bottomLeft=Node(isLeaf=True, val=False), bottomRight=Node(isLeaf=True, val=True)) Explanation: The grid has mixed values, so it splits into four 1×1 quadrants, each becoming a leaf.

Example 4:

Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]] Output: Node(isLeaf=False, val=True, topLeft=Node(isLeaf=True, val=True), topRight=Node(isLeaf=True, val=False), bottomLeft=Node(isLeaf=True, val=False), bottomRight=Node(isLeaf=True, val=True)) Explanation: Each 2×2 quadrant is uniform, so each becomes a leaf node.