題目
難度：★★☆☆☆
類型：二叉樹
四叉樹是一種樹數據，其中每個結點恰好有四個子結點：topLeft充坑、topRight俱尼、bottomLeft 和 bottomRight矮台。四叉樹通常被用來劃分一個二維空間锰悼，遞歸地將其細分為四個象限或區(qū)域。
我們希望在四叉樹中存儲 True/False 信息熊泵。四叉樹用來表示 N * N 的布爾網格仰迁。對于每個結點, 它將被等分成四個孩子結點直到這個區(qū)域內的值都是相同的。每個節(jié)點都有另外兩個布爾屬性：isLeaf 和 val顽分。當這個節(jié)點是一個葉子結點時 isLeaf 為真徐许。val 變量儲存葉子結點所代表的區(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
你的任務是實現一個函數绊寻，該函數根據兩個四叉樹返回表示這兩個四叉樹的邏輯或(或并)的四叉樹。
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 的網格悬秉。
N 將確保是 2 的整次冪澄步。
如果你想了解更多關于四叉樹的知識，你可以參考這個 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ū)留言~
