Construct Quad Tree
Given an `n x n` matrix `grid` of `0`s and `1`s (where `n` is a power of 2), build its **Quad-Tree** representation. A Quad-Tree node has six fields: - `val` (boolean): `true` if the region the node represents is all `1`s, `false` if all `0`s. For an internal node the `val` may be set to any value (test code ignores it on internal nodes). - `isLeaf` (boolean): `true` if the node is a leaf, `false` otherwise. - `topLeft`, `topRight`, `bottomLeft`, `bottomRight`: the four child nodes (or `null` on a leaf). Build the tree as follows: if the current region is uniform (all the same value), return a single leaf node holding that value. Otherwise split the region into four equal quadrants, recurse on each, and return an internal node whose four children are those subtrees. Implement `function construct(grid)` returning the **root** node. Represent each node as an object `{ val, isLeaf, topLeft, topRight, bottomLeft, bottomRight }`.
grid = [[0,1],[1,0]]→internal node with 4 leaves: TL=0, TR=1, BL=1, BR=0— The 2x2 region is not uniform, so it splits into four 1x1 leaves.grid = [[1,1],[1,1]]→single leaf, isLeaf=true, val=true— Entire region is all 1s -> one leaf.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]]→internal root; TL leaf(1), TR internal, BL leaf(1), BR leaf(0)— The top-right 4x4 quadrant is mixed, so it splits further.
- · n == grid.length == grid[i].length
- · n == 2^x where 0 <= x <= 6
- · grid[i][j] is 0 or 1