Medium

Quiz

#558 Logical OR of Two Binary Grids Represented as Quad-Trees

APPROACH

Two Quad-Trees, quadTree1 and quadTree2, each encode an n * n binary matrix. Return a Quad-Tree that represents the cell-wise logical OR of the two matrices. When isLeaf is False the val may be any value.

Each Quad-Tree node has:
- val: True when the region is all 1s; False when all 0s (relevant only for leaf nodes).
- isLeaf: True for uniform regions; False otherwise (node has four children).

Building a Quad-Tree: if the current region is uniform, make it a leaf with that value; otherwise split into four quadrants and recurse.

Serialization uses level-order traversal with null for absent nodes. Each node is encoded as [isLeaf, val] using 1 for True and 0 for False.

Example 1:

class Node {

public boolean val;

public boolean isLeaf;

public Node topLeft;

public Node topRight;

public Node bottomLeft;

public Node bottomRight;

}

Example 2:

Input: quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]

, quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]

Output: [[0,0],[1,1],[1,1],[1,1],[1,0]]

Explanation: quadTree1 and quadTree2 are shown above. You can see the binary matrix which is represented by each Quad-Tree.

If we apply logical bitwise OR on the two binary matrices we get the binary matrix below which is represented by the result Quad-Tree.

Notice that the binary matrices shown are only for illustration, you don't have to construct the binary matrix to get the result tree.

Example 3:

Input: quadTree1 = [[1,0]], quadTree2 = [[1,0]]

Output: [[1,0]]

Explanation: Each tree represents a binary matrix of size 1*1. Each matrix contains only zero.

The resulting matrix is of size 1*1 with also zero.

1 of 4

1:00

What is the optimal approach for this problem?