当前位置：首页 > news >正文

力扣面试150题--建立四叉树

news 2025/7/17 6:57:33

Day 77

题目描述

在这里插入图片描述

思路

经典中翻中：
这题的意思是：一个n*n的二维数组,n取的都是2的次方（方便分块）
将这个二维数组大小相同的分为4块，左上那一块数组表示topLeft,右上那块表示topRight,左下那块表示bottomLeft，右下那块表示bottomRight
好接下来，我们来关心分块后的数组，
**如果数组中所有元素都是1或者0，说明这就是个叶子节点，**它的值为1或者0（看数组中的值，记得转化为boolean）
如果分块后的数组的元素不全为0或者1，说明这个是个非叶节点，那就继续分块，最终分为所有元素相同的数组或者就一块
我们需要返回的就是头节点

思路：
这题细看是比较复杂的，那我们先抽取我们能干的事情：
对我而言，简单的事情是，我们需要判断一个二维数组是否全为一个值，这是判断这个节点是否为叶子节点的关键，于是我先编写了以下代码：
我们需要的参数有二维数组（grid），左上第一个元素的坐标（x，y），这个快数组的长宽（size）

 public boolean panleaf(int[][]grid,int x,int y,int size){//判断这一块是不是叶子节点if(size==1){return true;}int sum=grid[x][y];for(int i=x;i<x+size;i++){for(int j=y;j<y+size;j++){if(grid[i][j]!=sum){return false;}}}return true;}

接下来，我们来考虑，这肯定是一个递归的关系，那么首先思考
终止条件：如果是叶子节点，我们还需要递归吗？不需要，所有如果是叶子就终止。
那么如果不是叶子节点，那么就得分为四块，这不就是递归关系，因此有以下代码。

 public Node zao(int[][]grid,int x,int y,int size){if(panleaf(grid,x,y,size)){Node h=new Node(grid[x][y]==1,true);//这是一个叶子return h;}Node h=new Node(grid[x][y]==1,false);//这是一个节点h.topLeft=zao(grid,x,y,size/2);//toplefth.topRight=zao(grid,x,y+size/2,size/2);//toprighth.bottomLeft=zao(grid,x+size/2,y,size/2);//bottomlefth.bottomRight=zao(grid,x+size/2,y+size/2,size/2);//bottomrightreturn h;}

完整代码

/*
// Definition for a QuadTree node.
class Node {public boolean val;public boolean isLeaf;public Node topLeft;public Node topRight;public Node bottomLeft;public Node bottomRight;public Node() {this.val = false;this.isLeaf = false;this.topLeft = null;this.topRight = null;this.bottomLeft = null;this.bottomRight = null;}public Node(boolean val, boolean isLeaf) {this.val = val;this.isLeaf = isLeaf;this.topLeft = null;this.topRight = null;this.bottomLeft = null;this.bottomRight = null;}public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {this.val = val;this.isLeaf = isLeaf;this.topLeft = topLeft;this.topRight = topRight;this.bottomLeft = bottomLeft;this.bottomRight = bottomRight;}
}
*/class Solution {public Node construct(int[][] grid) {// public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) 构造函数return zao(grid,0,0,grid.length);}public Node zao(int[][]grid,int x,int y,int size){if(panleaf(grid,x,y,size)){Node h=new Node(grid[x][y]==1,true);//这是一个叶子return h;}Node h=new Node(grid[x][y]==1,false);//这是一个节点h.topLeft=zao(grid,x,y,size/2);//toplefth.topRight=zao(grid,x,y+size/2,size/2);//toprighth.bottomLeft=zao(grid,x+size/2,y,size/2);//bottomlefth.bottomRight=zao(grid,x+size/2,y+size/2,size/2);//bottomrightreturn h;}public boolean panleaf(int[][]grid,int x,int y,int size){//判断这一块是不是叶子节点if(size==1){return true;}int sum=grid[x][y];for(int i=x;i<x+size;i++){for(int j=y;j<y+size;j++){if(grid[i][j]!=sum){return false;}}}return true;}
}