427. Construct Quad Tree

Practice Construct Quad Tree for free on NudgeCode: Medium, Binary Tree pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

grid is an n x n matrix of 0s and 1s, where n is a power of two. Build its quad tree and return the root.

Every quad tree node has two attributes and four children:

• val: True if the node stands for a square of 1s, False for a square of 0s
• isLeaf: True if the node has no children
• topLeft, topRight, bottomLeft, bottomRight: the four children

Build the tree for a square like this:

1. If every cell in the square has the same value, return a leaf: isLeaf = True, val = that value, all four children null.
2. Otherwise return a node with isLeaf = False whose four children are the quad trees of the four equal quarters of the square (top-left, top-right, bottom-left, bottom-right). The val of a non-leaf node can be either value.

The tests write the tree in level order, one [isLeaf, val] pair per node with 1/0 for true/false. The four children of a leaf are written as null, and trailing nulls are removed. Non-leaf nodes are always written as [0,1], whatever val you give them.

Example

grid = [[0,1],[1,0]]  ->  [[0,1],[1,0],[1,1],[1,1],[1,0]]

The cells differ, so the root is not a leaf. Its four children are the single cells 0, 1, 1, 0.

Constraints

• n == grid.length == grid[i].length
• n == 2^x with 0 <= x <= 6
• grid[i][j] is 0 or 1