Build a QuadTree From a Grid

Implement a compressed QuadTree for a square grid.

You are given an n x n grid of values, where n is a power of two. The values are not limited to binary values; they may be any comparable type such as integers or strings.

Define a QuadTree node with:

• value: the value stored for a leaf region. For non-leaf nodes, this may be any placeholder value.
• isLeaf: whether this node represents a uniform region.
• topLeft, topRight, bottomLeft, bottomRight: child pointers, all null for a leaf node.

Build and return the root of a compressed QuadTree using the following rules:

1. A region is represented by a leaf node if every cell in that region has the same value.
2. Otherwise, split the region into four equal quadrants and recursively build child nodes for each quadrant.
3. The root represents the entire grid.

Example:

Input:

[
  [1, 1, 2, 2],
  [1, 1, 2, 2],
  [3, 3, 4, 4],
  [3, 3, 4, 4]
]

Output: an internal root node with four leaf children, whose values are 1, 2, 3, and 4 for the top-left, top-right, bottom-left, and bottom-right quadrants respectively.

Implement the data structure and the buildQuadTree(grid) function.

Build a QuadTree From a Grid

Given a non-empty n x n grid, where n is a power of two, build a compressed QuadTree for the whole grid.

A region should be represented by a leaf node if every cell in that region has the same value. Otherwise, split the region into four equal quadrants and recursively build child nodes in this order: top-left, top-right, bottom-left, bottom-right.

For deterministic judging, return the tree as a nested Python dictionary with exactly these keys: value, isLeaf, topLeft, topRight, bottomLeft, bottomRight.

Rules for the returned structure:

• Leaf node: isLeaf is True, value is the region's value, and all four child fields are None.
• Internal node: isLeaf is False, value must be None, and all four child fields contain child nodes.

You may implement a custom Node class internally if you want, but the final return value from solution(grid) must follow the nested dictionary format above.

Constraints

• 1 <= n <= 64
• n is a power of two
• Each row of grid has length n
• Values support equality comparison

Hints

1. Use divide-and-conquer recursion on square sub-regions of the grid.
2. Before splitting a region, scan it to check whether all cells are equal; as soon as you find a different value, you can stop and split.