題目

難度：★★☆☆☆
類型：二叉樹

四叉樹是一種樹數(shù)據(jù)，其中每個結(jié)點恰好有四個子結(jié)點：topLeft、topRight、bottomLeft 和 bottomRight。四叉樹通常被用來劃分一個二維空間，遞歸地將其細(xì)分為四個象限或區(qū)域。

我們希望在四叉樹中存儲 True/False 信息。四叉樹用來表示 N * N 的布爾網(wǎng)格。對于每個結(jié)點, 它將被等分成四個孩子結(jié)點直到這個區(qū)域內(nèi)的值都是相同的。每個節(jié)點都有另外兩個布爾屬性：isLeaf 和 val。當(dāng)這個節(jié)點是一個葉子結(jié)點時 isLeaf 為真。val 變量儲存葉子結(jié)點所代表的區(qū)域的值。

例如，下面是兩個四叉樹 A 和 B：

A:
+-------+-------+   T: true
|       |       |   F: false
|   T   |   T   |
|       |       |
+-------+-------+
|       |       |
|   F   |   F   |
|       |       |
+-------+-------+

topLeft: T
topRight: T
bottomLeft: F
bottomRight: F

B:
+-------+---+---+
|       | F | F |
|   T   +---+---+
|       | T | T |
+-------+---+---+
|       |       |
|   T   |   F   |
|       |       |
+-------+-------+

topLeft: T
topRight:
     topLeft: F
     topRight: F
     bottomLeft: T
     bottomRight: T
bottomLeft: T
bottomRight: F

你的任務(wù)是實現(xiàn)一個函數(shù)，該函數(shù)根據(jù)兩個四叉樹返回表示這兩個四叉樹的邏輯或(或并)的四叉樹。

A:                 B:                 C (A or B):
+-------+-------+  +-------+---+---+  +-------+-------+
|       |       |  |       | F | F |  |       |       |
|   T   |   T   |  |   T   +---+---+  |   T   |   T   |
|       |       |  |       | T | T |  |       |       |
+-------+-------+  +-------+---+---+  +-------+-------+
|       |       |  |       |       |  |       |       |
|   F   |   F   |  |   T   |   F   |  |   T   |   F   |
|       |       |  |       |       |  |       |       |
+-------+-------+  +-------+-------+  +-------+-------+

提示

A 和 B 都表示大小為 N * N 的網(wǎng)格。
N 將確保是 2 的整次冪。
如果你想了解更多關(guān)于四叉樹的知識，你可以參考這個 wiki 頁面。
邏輯或的定義如下：如果 A 為 True ，或者 B 為 True ，或者 A 和 B 都為 True，則 "A 或 B" 為 True。

解答

# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight


class Solution(object):
    def intersect(self, quadTree1, quadTree2):
        """
        :type quadTree1: Node
        :type quadTree2: Node
        :rtype: Node
        """
        if (quadTree1.isLeaf and quadTree1.val) or (quadTree2.isLeaf and not quadTree2.val):
            return quadTree1
        elif (quadTree2.isLeaf and quadTree2.val) or (quadTree1.isLeaf and not quadTree1.val):
            return quadTree2
        else:
            l1 = self.intersect(quadTree1.topLeft,quadTree2.topLeft)
            l2 = self.intersect(quadTree1.topRight,quadTree2.topRight)
            l3 = self.intersect(quadTree1.bottomLeft,quadTree2.bottomLeft)
            l4 = self.intersect(quadTree1.bottomRight,quadTree2.bottomRight)
            if l1.isLeaf and l2.isLeaf and l3.isLeaf and l4.isLeaf and l1.val == l2.val == l3.val == l4.val:
                return l1
            return Node(None,False,l1,l2,l3,l4)

如有疑問或建議，歡迎評論區(qū)留言~