难度: Easy
原题连接
内容描述
A quadtree is a tree data in which each internal node has exactly four children: topLeft, topRight, bottomLeft and bottomRight. Quad trees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
We want to store True/False information in our quad tree. The quad tree is used to represent a N * N boolean grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same. Each node has another two boolean attributes : isLeaf and val. isLeaf is true if and only if the node is a leaf node. The val attribute for a leaf node contains the value of the region it represents.
For example, below are two quad trees A and 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
Your task is to implement a function that will take two quadtrees and return a quadtree that represents the logical OR (or union) of the two trees.
A: B: C (A or B):
+-------+-------+ +-------+---+---+ +-------+-------+
| | | | | F | F | | | |
| T | T | | T +---+---+ | T | T |
| | | | | T | T | | | |
+-------+-------+ +-------+---+---+ +-------+-------+
| | | | | | | | |
| F | F | | T | F | | T | F |
| | | | | | | | |
+-------+-------+ +-------+-------+ +-------+-------+
Note:
Both A and B represent grids of size N * N.
N is guaranteed to be a power of 2.
If you want to know more about the quad tree, you can refer to its wiki.
The logic OR operation is defined as this: "A or B" is true if A is true, or if B is true, or if both A and B are true.
思路 1 - 时间复杂度: O(4^N)- 空间复杂度: O(N)******
这个题目描述的很不清楚, 总结了一下有以下几个规则：
- 一个Node如果是leaf的话，那么它的topLeft, topRight, bottomLeft and bottomRight肯定都是None, 但是它的val不一定是True；
- 一个Node如果是non-leaf的话，那么它的topLeft, topRight, bottomLeft and bottomRight中至少有一个不是None，并且它的val一定是False
- 如果两个leaf Node A和B做OR操作时，就要看它们的val做OR操作的结果了
- 如果结果是True，即A.val or B.val == True, 那么返回val为True的那一个Node
- 如果结果是False，随便返回哪个Node都一样，因为这两个Node现在都是leaf， 然后val都为False，topLeft, topRight, bottomLeft and bottomRight也肯定都是None
- 如果是一个non-leaf Node A和一个leaf Node B做OR操作
- 如果B.val == True，那么它们OR操作的结果必然是True的，所以返回Node B就可以了
- 如果B.val == False，那么OR操作结果一定是False，因为A是non-leaf Node，其val一定是False，所以我们直接返回Node A
- 如果两个non-leaf Node A 和 B做OR操作，那么我们要对他们的topLeft, topRight, bottomLeft and bottomRight分别做OR操作后才能得出结果
- 如果这4个返回结果的Node都是leaf Node的话，按照定义最终Node C就是一个leaf Node （因为它的topLeft, topRight, bottomLeft and bottomRight全是Leaf Node）， 此时如果C的topLeft, topRight, bottomLeft and bottomRight的val都相同的话，Node C的val就为True （因为它的topLeft, topRight, bottomLeft and bottomRight的val全部一样）
- 其他所有情况都直接返回一个non-leaf Node，按照规则2的定义就是Node(False, False, topLeft, topRight, bottomLeft, bottomRight)
发现可以直接参考第427题
beats 32.58%
class Solution(object):
def intersect(self, quadTree1, quadTree2):
"""
:type quadTree1: Node
:type quadTree2: Node
:rtype: Node
"""
if quadTree1.isLeaf and quadTree2.isLeaf:
if quadTree1.val:
return quadTree1
else:
return quadTree2
elif quadTree1.isLeaf and not quadTree2.isLeaf:
if quadTree1.val:
return quadTree1
else:
return quadTree2
elif not quadTree1.isLeaf and quadTree2.isLeaf:
if quadTree2.val:
return quadTree2
else:
return quadTree1
else:
topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)
bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)
children = [topLeft, topRight, bottomLeft, bottomRight]
values = [child.val for child in children]
leaves = [child.isLeaf for child in children]
if all(leaves) and (sum(values) == 0 or sum(values) == 4):
return Node(values[0], True, None, None, None, None)
# non-leaf must have False val
return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)最终我们发现前面3种情况可以写得更简洁一些
class Solution(object):
def intersect(self, quadTree1, quadTree2):
"""
:type quadTree1: Node
:type quadTree2: Node
:rtype: Node
"""
if quadTree1.isLeaf:
return quadTree1 if quadTree1.val else quadTree2
elif quadTree2.isLeaf:
return quadTree2 if quadTree2.val else quadTree1
else:
topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)
bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)
children = [topLeft, topRight, bottomLeft, bottomRight]
values = [child.val for child in children]
leaves = [child.isLeaf for child in children]
if all(leaves) and (sum(values) == 0 or sum(values) == 4):
return Node(values[0], True, None, None, None, None)
# non-leaf must have False val
return Node(False, False, topLeft, topRight, bottomLeft, bottomRight)