Construct Quad Tree
Advertisement
Problem
Construct a quad tree from an n×n binary matrix. If a region is all-same, it's a leaf. Otherwise split into 4.
Solutions
# Python
def construct(grid):
n = len(grid)
def build(r, c, size):
val = grid[r][c]
uniform = all(grid[r+i][c+j] == val for i in range(size) for j in range(size))
if uniform:
return Node(val == 1, True)
half = size // 2
node = Node(True, False)
node.topLeft = build(r, c, half)
node.topRight = build(r, c + half, half)
node.bottomLeft = build(r + half, c, half)
node.bottomRight = build(r + half, c + half, half)
return node
return build(0, 0, n)
// C++
Node* build(vector<vector<int>>& g, int r, int c, int sz) {
int v = g[r][c];
bool uniform = true;
for (int i=r;i<r+sz&&uniform;i++) for(int j=c;j<c+sz;j++) if(g[i][j]!=v){uniform=false;break;}
if (uniform) return new Node(v==1, true);
int h = sz/2;
auto node = new Node(true, false);
node->topLeft=build(g,r,c,h); node->topRight=build(g,r,c+h,h);
node->bottomLeft=build(g,r+h,c,h); node->bottomRight=build(g,r+h,c+h,h);
return node;
}
Node* construct(vector<vector<int>>& grid) { return build(grid,0,0,grid.size()); }
// Java
public Node construct(int[][] grid) { return build(grid, 0, 0, grid.length); }
Node build(int[][] g, int r, int c, int sz) {
int v = g[r][c]; boolean uni = true;
outer: for(int i=r;i<r+sz;i++) for(int j=c;j<c+sz;j++) if(g[i][j]!=v){uni=false;break outer;}
if (uni) return new Node(v==1,true);
int h=sz/2; Node n=new Node(true,false);
n.topLeft=build(g,r,c,h); n.topRight=build(g,r,c+h,h);
n.bottomLeft=build(g,r+h,c,h); n.bottomRight=build(g,r+h,c+h,h);
return n;
}
// JavaScript
function construct(grid) {
const n = grid.length;
function build(r, c, size) {
const val = grid[r][c];
let uniform = true;
outer: for (let i=r;i<r+size;i++) for(let j=c;j<c+size;j++) if(grid[i][j]!==val){uniform=false;break outer;}
if (uniform) return new Node(val===1, true);
const h = size>>1;
const node = new Node(true, false);
node.topLeft=build(r,c,h); node.topRight=build(r,c+h,h);
node.bottomLeft=build(r+h,c,h); node.bottomRight=build(r+h,c+h,h);
return node;
}
return build(0, 0, n);
}
Complexity
- Time: O(n^2 log n), Space: O(log n) recursion
Advertisement