二進(jìn)制矩陣中的所有元素不是 0 就是 1 划栓。
給你兩個四叉樹崖面，quadTree1 和 quadTree2屎勘。其中 quadTree1 表示一個 n * n 二進(jìn)制矩陣赡译，而 quadTree2 表示另一個 n * n 二進(jìn)制矩陣既们。
請你返回一個表示 n * n 二進(jìn)制矩陣的四叉樹濒析，它是 quadTree1 和 quadTree2 所表示的兩個二進(jìn)制矩陣進(jìn)行 按位邏輯或運(yùn)算 的結(jié)果。
注意啥纸，當(dāng) isLeaf 為 False 時号杏，你可以把 True 或者 False 賦值給節(jié)點(diǎn)，兩種值都會被判題機(jī)制 接受 斯棒。
四叉樹數(shù)據(jù)結(jié)構(gòu)中盾致，每個內(nèi)部節(jié)點(diǎn)只有四個子節(jié)點(diǎn)。此外荣暮，每個節(jié)點(diǎn)都有兩個屬性：
val：儲存葉子結(jié)點(diǎn)所代表的區(qū)域的值庭惜。1 對應(yīng) True，0 對應(yīng) False穗酥；
isLeaf: 當(dāng)這個節(jié)點(diǎn)是一個葉子結(jié)點(diǎn)時為 True护赊，如果它有 4 個子節(jié)點(diǎn)則為 False 惠遏。
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}
我們可以按以下步驟為二維區(qū)域構(gòu)建四叉樹：
如果當(dāng)前網(wǎng)格的值相同（即，全為 0 或者全為 1）骏啰，將 isLeaf 設(shè)為 True 节吮，將 val 設(shè)為網(wǎng)格相應(yīng)的值，并將四個子節(jié)點(diǎn)都設(shè)為 Null 然后停止判耕。
如果當(dāng)前網(wǎng)格的值不同透绩，將 isLeaf 設(shè)為 False， 將 val 設(shè)為任意值壁熄，然后如下圖所示帚豪，將當(dāng)前網(wǎng)格劃分為四個子網(wǎng)格。
使用適當(dāng)?shù)淖泳W(wǎng)格遞歸每個子節(jié)點(diǎn)草丧。
class Solution {
public Node intersect(Node quadTree1, Node quadTree2) {
if (quadTree1.isLeaf) {
if (quadTree1.val) {
return new Node(true, true);
}
return new Node(quadTree2.val, quadTree2.isLeaf, quadTree2.topLeft, quadTree2.topRight, quadTree2.bottomLeft, quadTree2.bottomRight);
}
if (quadTree2.isLeaf) {
return intersect(quadTree2, quadTree1);
}
Node o1 = intersect(quadTree1.topLeft, quadTree2.topLeft);
Node o2 = intersect(quadTree1.topRight, quadTree2.topRight);
Node o3 = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
Node o4 = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
if (o1.isLeaf && o2.isLeaf && o3.isLeaf && o4.isLeaf && o1.val == o2.val && o1.val == o3.val && o1.val == o4.val) {
return new Node(o1.val, true);
}
return new Node(false, false, o1, o2, o3, o4);
}
}
