题目链接：https://leetcode.cn/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/
思路
方法一、分治递归
直接想法
四叉树相当于一个 n * n 的矩阵，四个节点又分成了父节点的矩阵的四个区域
- topLeft 节点为其父节点对应的矩阵区域左上角的 1/4 区域。
- topRight 节点为其父节点对应的矩阵区域右上角的 1/4 区域。
- bottomLeft 节点为其父节点对应的矩阵区域左下角的 1/4 区域。
- bottomRight 节点为其父节点对应的矩阵区域右下角的1/4 区域。
题目要求我们合并两颗四叉树 quadTree1 和 quadTree2，合并的方式就是把这矩阵中对应的四个区域的Val值进行 或 操作
或操作：x ∈ {0,1}, 0 | x = x, 1 | x = 1
所以我们需要把这两棵树对应的结合进行合并，设当前操作的两个结点为 node1 和 node2， 合并操作为 node1 | node2
1.node1是叶结点
1）node1.Val 为1 ，那么 node1 | node2 = 1
2）node1.Val 为0，那么 node1 | node2 = node2
2.node2是叶结点
1）node2.Val 为1 ，那么 node1 | node2 = 1
2）node2.Val 为0，那么 node1 | node2 = node1
3.两个结点都不是叶结点，则我们需要对两个结点的四个子节点分别进行分治递归操作，重复上面合并操作，然后再判断合并后的四个子结点是否对应的区域值都为全0 或者 全1，如果是则合并结点为叶子节点，反之则不是叶子节点，且四个子节点的值为上面合并操作后的四个对应子节点值
代码示例
/** * Definition for a QuadTree node. * type Node struct { * Val bool * IsLeaf bool * TopLeft *Node * TopRight *Node * BottomLeft *Node * BottomRight *Node * } */ func intersect(quadTree1, quadTree2 *Node) *Node { //node1是叶子节点 if quadTree1.IsLeaf { //node1值为1,则直接合并 if quadTree1.Val { return &Node{Val: true, IsLeaf: true} } //node1 | node2 = node2 return quadTree2 } //node2是叶子节点 if quadTree2.IsLeaf { //合并两个结点 return intersect(quadTree2, quadTree1) } //合并左上区域 TL := intersect(quadTree1.TopLeft, quadTree2.TopLeft) //合并右上区域 TR := intersect(quadTree1.TopRight, quadTree2.TopRight) //合并左下区域 BL := intersect(quadTree1.BottomLeft, quadTree2.BottomLeft) //合并右下区域 BR := intersect(quadTree1.BottomRight, quadTree2.BottomRight) //判断当前结点是否都是叶子结点并且是否为全0或全1 if TL.IsLeaf && TR.IsLeaf && BL.IsLeaf && BR.IsLeaf && TL.Val == TR.Val && TL.Val == BL.Val && TL.Val == BR.Val { return &Node{Val: TL.Val, IsLeaf: true} } return &Node{false, false, TL, TR, BL, BR} }
复杂度分析
- 时间复杂度：O(n2)，其中 n 是四叉树 quadTree1 和 quadTree2 对应矩阵的边长。最坏的情况下，整个矩阵都会被遍历。
- 空间复杂度：O(logn)，其中 n 是四叉树 quadTree1 和 quadTree2 对应矩阵的边长。空间开销主要为递归的空间开销。
