算法题：建立四叉树
0 和 1 的组合，目的是把这矩阵压缩成一棵四叉树。虽然看着麻烦，但其实套路还是有的，整起来并不复杂。0 或全是 1），那就是叶子节点；如果不一样，那就要继续分，直到每块区域里都“统一思想”。class Node {
public boolean val; // 节点的值
public boolean isLeaf; // 是否是叶子节点
public Node topLeft, topRight, bottomLeft, bottomRight;
public Node(boolean val, boolean isLeaf) {
this.val = val;
this.isLeaf = isLeaf;
}
}
public class QuadTree {
public Node construct(int[][] grid) {
return buildTree(grid, 0, 0, grid.length);
}
private Node buildTree(int[][] grid, int row, int col, int size) {
if (size == 1) { // 如果是 1x1 的小矩阵，直接返回叶子节点
return new Node(grid[row][col] == 1, true);
}
int newSize = size / 2;
Node topLeft = buildTree(grid, row, col, newSize);
Node topRight = buildTree(grid, row, col + newSize, newSize);
Node bottomLeft = buildTree(grid, row + newSize, col, newSize);
Node bottomRight = buildTree(grid, row + newSize, col + newSize, newSize);
// 如果四个子节点的值和叶子属性都一样，可以合并成一个节点
if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf &&
topLeft.val == topRight.val &&
topRight.val == bottomLeft.val &&
bottomLeft.val == bottomRight.val) {
return new Node(topLeft.val, true);
}
// 否则创建一个非叶子节点
Node root = new Node(false, false);
root.topLeft = topLeft;
root.topRight = topRight;
root.bottomLeft = bottomLeft;
root.bottomRight = bottomRight;
return root;
}
}
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
