leetcode：558. 四叉树交集【四叉树dfs】

分析

它的意思是让两个四叉树每个小方格对应的值取交让后返回的四叉树
显然返回情况就是当一方是叶子的时候
如果一方是叶子，它的方格里面的值都一样，如果都是1，就返回一个全1的叶子；如果都是0，那么就返回不是叶子的另外一个四叉树
然后第二种情况就是dfs，因为都不是叶子，所以可以把四个角的交集都求出来，然后如果他们都是叶子且值都相等就可以合并成一个大的叶子，否则，就正常的生成四叉

ac code

""" # 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:
    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':
        # 有一个叶子
        if quadTree1.isLeaf:
            return Node(quadTree1.val, True) if quadTree1.val else quadTree2
        if quadTree2.isLeaf:
            # 优雅
            return self.intersect(quadTree2, quadTree1)
        

        # 都不是叶子
        o1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft)
        o2 = self.intersect(quadTree1.topRight, quadTree2.topRight)
        o3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)
        o4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)

        # 如果四个位置都可以变成相同的叶子
        if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val == o2.val == o3.val == o4.val:
            return Node(o1.val, True)
        
        return Node(False, False, o1, o2, o3, o4)

总结

来自四叉树的dfs