分治题目：建立四叉树

文章目录题目标题和出处难度题目描述要求四叉树格式示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题建立四叉树出处427. 建立四叉树难度5 级题目描述要求给定一个n × n \texttt{n} \times \texttt{n}n×n的矩阵grid \texttt{grid}grid矩阵由若干0 \texttt{0}0和1 \texttt{1}1组成。要求用四叉树表示该矩阵grid \texttt{grid}grid。返回能表示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输入grid [[0,1],[1,0]] \texttt{grid [[0,1],[1,0]]}grid [[0,1],[1,0]]输出[[0,1],[1,0],[1,1],[1,1],[1,0]] \texttt{[[0,1],[1,0],[1,1],[1,1],[1,0]]}[[0,1],[1,0],[1,1],[1,1],[1,0]]解释此示例的解释如下请注意在下面四叉树的图示中0 \texttt{0}0表示false \texttt{false}false1 \texttt{1}1表示true \texttt{true}true。示例 2输入grid [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]] \texttt{grid [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]}grid [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]输出[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]] \texttt{[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]}[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]解释网格中的所有值都不相同。我们将网格划分为四个子网格。topLeft \texttt{topLeft}topLeft、bottomLeft \texttt{bottomLeft}bottomLeft和bottomRight \texttt{bottomRight}bottomRight均具有相同的值。topRight \texttt{topRight}topRight具有不同的值因此我们将其再分为4 \texttt{4}4个子网格这样每个子网格都具有相同的值。解释如下图所示数据范围n grid.length grid[i].length \texttt{n} \texttt{grid.length} \texttt{grid[i].length}ngrid.lengthgrid[i].lengthn 2 x \texttt{n} \texttt{2}^\texttt{x}n2x其中0 ≤ x ≤ 6 \texttt{0} \le \texttt{x} \le \texttt{6}0≤x≤6解法思路和算法根据定义四叉树中的每个结点都对应一个矩阵矩阵的行数和列数相同且为2 22的非负整数次幂每个结点的情况如下。如果一个结点对应的矩阵的边长等于1 11则该结点是叶结点结点值为矩阵中的唯一元素值。如果一个结点对应的矩阵的边长大于1 11则该结点可能是叶结点或非叶结点。如果该结点的四个子结点都是叶结点且值相同则该结点是叶结点否则该结点是非叶结点。由于题目规定非叶结点的值可以任取因此判断一个结点是否为叶结点时需要同时考虑其四个子结点是否为叶结点和四个子结点的值是否相同。此处将非叶结点的值设为其四个子结点的值的逻辑或运算的结果。使用边长为n nn的矩阵grid \textit{grid}grid构造四叉树时如果当前结点对应的矩阵边长大于1 11则首先构建当前结点的四个子结点然后根据子结点的值构建当前结点。这是一个递归分治的过程。分治的终止条件是n 1 n 1n1此时四叉树中唯一的结点是叶结点结点值为矩阵中的唯一元素值。当n 1 n 1n1时递归地构建当前结点的四个子结点然后根据四个子结点构建当前结点构建当前结点的做法如下。如果四个子结点都是叶结点且值相同则当前结点是叶结点其值为四个子结点值的逻辑或运算的结果将当前结点的子结点设为空。否则当前结点不是叶结点其值为四个子结点值的逻辑或运算的结果将四个子结点作为当前结点的四个子结点。使用原始矩阵grid \textit{grid}grid根据上述做法构建四叉树即可得到完整的四叉树。代码classSolution{publicNodeconstruct(int[][]grid){returnconstruct(grid,0,0,grid.length);}publicNodeconstruct(int[][]grid,intstartRow,intstartCol,intside){if(side1){returnnewNode(grid[startRow][startCol]1,true);}inthalfSideside/2;NodetopLeftconstruct(grid,startRow,startCol,halfSide);NodetopRightconstruct(grid,startRow,startColhalfSide,halfSide);NodebottomLeftconstruct(grid,startRowhalfSide,startCol,halfSide);NodebottomRightconstruct(grid,startRowhalfSide,startColhalfSide,halfSide);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是矩阵grid \textit{grid}grid的边长。分治的递归调用栈共有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是矩阵grid \textit{grid}grid的边长。递归调用栈需要O ( log ⁡ n ) O(\log n)O(logn)的空间。注意返回值不计入空间复杂度。