文章目录题目标题和出处难度题目描述要求四叉树格式示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题四叉树交集出处558. 四叉树交集难度5 级题目描述要求二进制矩阵中的所有元素都是0 \texttt{0}0或1 \texttt{1}1。给定两个四叉树quadTree1 \texttt{quadTree1}quadTree1和quadTree2 \texttt{quadTree2}quadTree2分别代表一个n × n \texttt{n} \times \texttt{n}n×n的二进制矩阵。返回一个表示n × n \texttt{n} \times \texttt{n}n×n二进制矩阵的四叉树返回的四叉树是quadTree1 \texttt{quadTree1}quadTree1和quadTree2 \texttt{quadTree2}quadTree2所表示的两个二进制矩阵进行逻辑或运算的结果。返回能表示grid \texttt{grid}grid的四叉树的根结点。四叉树数据结构中每个内部结点恰好有四个子结点。此外每个结点都有两个属性val \texttt{val}val储存叶结点所代表的区域的值1 \texttt{1}1对应true \texttt{true}true0 \texttt{0}0对应false \texttt{false}false。isLeaf \texttt{isLeaf}isLeaf当这个结点是叶结点时为true \texttt{true}true当这个结点有4 \texttt{4}4个子结点时为false \texttt{false}false。注意当isLeaf \texttt{isLeaf}isLeaf为false \texttt{false}false时可以把true \texttt{true}true或者false \texttt{false}false赋值给val \texttt{val}val两种值都是允许的。class Node { public boolean val; public boolean isLeaf; public Node topLeft; public Node topRight; public Node bottomLeft; public Node bottomRight; }按以下步骤为二维区域构建四叉树如果当前网格的值相同即全为0 \texttt{0}0或者全为1 \texttt{1}1将isLeaf \texttt{isLeaf}isLeaf设为true \texttt{true}true将val \texttt{val}val设为网格相应的值并将四个子结点都设为null \texttt{null}null然后停止。如果当前网格的值不同将isLeaf \texttt{isLeaf}isLeaf设为false \texttt{false}false将val \texttt{val}val设为任意值然后如下图所示将当前网格划分为四个子网格。使用适当的子网格递归每个子结点。四叉树格式输出为使用层序遍历后四叉树的序列化形式其中null \texttt{null}null表示路径终止符其下面不存在结点。它与二叉树的序列化非常相似。唯一的区别是结点以列表形式表示[isLeaf, val] \texttt{[isLeaf, val]}[isLeaf, val]。如果isLeaf \texttt{isLeaf}isLeaf或者val \texttt{val}val的值为true \texttt{true}true则表示它在列表[isLeaf, val] \texttt{[isLeaf, val]}[isLeaf, val]中的值为1 \texttt{1}1如果isLeaf \texttt{isLeaf}isLeaf或者val \texttt{val}val的值为false \texttt{false}false则表示值为0 \texttt{0}0。示例示例 1输入quadTree1 [[0,1],[1,1],[1,1],[1,0],[1,0]] , quadTree2 [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]] \texttt{quadTree1 [[0,1],[1,1],[1,1],[1,0],[1,0]] , quadTree2 [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]}quadTree1 [[0,1],[1,1],[1,1],[1,0],[1,0]] , quadTree2 [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]输出[[0,0],[1,1],[1,1],[1,1],[1,0]] \texttt{[[0,0],[1,1],[1,1],[1,1],[1,0]]}[[0,0],[1,1],[1,1],[1,1],[1,0]]解释quadTree1 \texttt{quadTree1}quadTree1和quadTree2 \texttt{quadTree2}quadTree2如上所示。由四叉树所表示的二进制矩阵也已经给出。如果对这两个矩阵进行逻辑或运算则可以得到下面的二进制矩阵由一个作为结果的四叉树表示。这里展示的二进制矩阵仅仅是为了更好地说明题意不需要构造二进制矩阵来获得结果四叉树。示例 2输入quadTree1 [[1,0]], quadTree2 [[1,0]] \texttt{quadTree1 [[1,0]], quadTree2 [[1,0]]}quadTree1 [[1,0]], quadTree2 [[1,0]]输出[[1,0]] \texttt{[[1,0]]}[[1,0]]解释两个树所表示的矩阵大小都是1 × 1 \texttt{1} \times \texttt{1}1×1值都是0 \texttt{0}0。结果矩阵大小是1 × 1 \texttt{1} \times \texttt{1}1×1值都是0 \texttt{0}0。数据范围quadTree1 \texttt{quadTree1}quadTree1和quadTree2 \texttt{quadTree2}quadTree2都是有效的四叉树每个四叉树分别代表一个n × n \texttt{n} \times \texttt{n}n×n的矩阵n 2 x \texttt{n} \texttt{2}^\texttt{x}n2x其中0 ≤ x ≤ 9 \texttt{0} \le \texttt{x} \le \texttt{9}0≤x≤9解法思路和算法根据定义四叉树中的每个结点都对应一个矩阵矩阵的行数和列数相同且为2 22的非负整数次幂每个结点的情况如下。如果一个结点对应的矩阵的边长等于1 11则该结点是叶结点结点值为矩阵中的唯一元素值。如果一个结点对应的矩阵的边长大于1 11则该结点可能是叶结点或非叶结点。如果该结点的四个子结点都是叶结点且值相同则该结点是叶结点否则该结点是非叶结点。由于题目规定非叶结点的值可以任取因此判断一个结点是否为叶结点时需要同时考虑其四个子结点是否为叶结点和四个子结点的值是否相同。此处将非叶结点的值设为其四个子结点的值的逻辑或运算的结果。这道题要求计算给定的两个相同大小的四叉树quadTree 1 \textit{quadTree}_1quadTree1​和quadTree 2 \textit{quadTree}_2quadTree2​的逻辑或运算的结果。如果两个四叉树的当前结点对应的矩阵边长大于1 11则分别对两个四叉树的当前结点的四个子结点计算逻辑或运算的结果然后对两个四叉树计算逻辑或运算的结果。这是一个递归分治的过程。分治的终止条件是两个四叉树中至少有一个四叉树的根结点是叶结点此时可以直接返回结果。如果是叶结点的根结点的值是true \text{true}true则结果四叉树只有根结点根结点的值是true \text{true}true且根结点是叶结点。如果是叶结点的根结点的值是false \text{false}false则结果四叉树为另一个四叉树的根结点。其余情况下递归地计算两个四叉树的当前结点的四个子结点的逻辑或运算的结果即结果四叉树的当前结点的四个子结点然后根据结果四叉树的当前结点的四个子结点构建结果四叉树的当前结点构建结果四叉树的当前结点的做法如下。如果结果四叉树的当前结点的四个子结点都是叶结点且值相同则结果四叉树的当前结点是叶结点其值为四个子结点值的逻辑或运算的结果将结果四叉树的当前结点的子结点设为空。否则结果四叉树的当前结点不是叶结点其值为四个子结点值的逻辑或运算的结果将计算得到的四个子结点作为当前结点的四个子结点。从quadTree 1 \textit{quadTree}_1quadTree1​和quadTree 2 \textit{quadTree}_2quadTree2​的根结点开始计算逻辑或运算的结果即可得到完整的结果四叉树。代码classSolution{publicNodeintersect(NodequadTree1,NodequadTree2){if(quadTree1.isLeaf){returnquadTree1.val?newNode(true,true):quadTree2;}if(quadTree2.isLeaf){returnquadTree2.val?newNode(true,true):quadTree1;}NodetopLeftintersect(quadTree1.topLeft,quadTree2.topLeft);NodetopRightintersect(quadTree1.topRight,quadTree2.topRight);NodebottomLeftintersect(quadTree1.bottomLeft,quadTree2.bottomLeft);NodebottomRightintersect(quadTree1.bottomRight,quadTree2.bottomRight);booleanvaltopLeft.val||topRight.val||bottomLeft.val||bottomRight.val;booleanisLeaftopLeft.isLeaftopRight.isLeafbottomLeft.isLeafbottomRight.isLeaftopLeft.valtopRight.valtopLeft.valbottomLeft.valtopLeft.valbottomRight.val;returnisLeaf?newNode(val,isLeaf):newNode(val,isLeaf,topLeft,topRight,bottomLeft,bottomRight);}}复杂度分析时间复杂度O ( n 2 ) O(n^2)O(n2)其中n nn是四叉树quadTree 1 \textit{quadTree}_1quadTree1​和quadTree 2 \textit{quadTree}_2quadTree2​表示的二进制矩阵的边长。分治的递归调用栈共有O ( log ⁡ n ) O(\log n)O(logn)层第k kk层调用时需要处理的结点数是O ( 4 k ) O(4^k)O(4k)需要处理的结点总数是O ( n 2 ) O(n^2)O(n2)每个结点的处理时间是O ( 1 ) O(1)O(1)因此时间复杂度是O ( n 2 ) O(n^2)O(n2)。空间复杂度O ( log ⁡ n ) O(\log n)O(logn)其中n nn是四叉树quadTree 1 \textit{quadTree}_1quadTree1​和quadTree 2 \textit{quadTree}_2quadTree2​表示的二进制矩阵的边长。递归调用栈需要O ( log ⁡ n ) O(\log n)O(logn)的空间。注意返回值不计入空间复杂度。