https://leetcode.com/problems/construct-quad-tree/ 四叉樹維基 四叉樹簡介:
好處在做搜尋時比較快。
O(n) -> O(h) // h為樹的高度 //n 為總數
Leet Code 四叉樹建立分享
簡單來說就是用遞迴去跑 8->4->2->1 以此類推
step 1. 判斷是否全 0 or 全 1 如果是 isLeaf = true, reutrn node
step 2. 如果不是把它分成4等份 呼叫遞迴
step 3. 一直到拆分到只剩 1 為止
/*
// Definition for a QuadTree node.
public class Node {
public bool val;
public bool isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
public Node() {
val = false;
isLeaf = false;
topLeft = null;
topRight = null;
bottomLeft = null;
bottomRight = null;
}
public Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = null;
topRight = null;
bottomLeft = null;
bottomRight = null;
}
public Node(bool _val,bool _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
}
*/
public class Solution {
public Node Construct(int[][] grid)
{
if (grid == null)
{
return null;
}
Node root = new Node();
root = Link(grid);
return root;
}
public Node Link(int[][] grid)
{
Node n = new Node();
if (grid.Length == 1)
{
n.val = grid[0][0] == 1;
n.isLeaf = true;
return n;
}
int size = grid.Length;
int halfSize = size / 2;
bool all1 = true;
bool all0 = true;
for (int x = 0; x < size; x++)
{
for (int y = 0; y < size; y++)
{
all0 = all0 && grid[x][y] == 0;
all1 = all1 && grid[x][y] == 1;
}
}
if (all1)
{
n.val = true;
n.isLeaf = true;
return n;
}
if (all0)
{
n.val = false;
n.isLeaf = true;
return n;
}
int[][] topleft = new int[halfSize][];
for (int x = 0; x < halfSize; x++)
{
for (int y = 0; y < halfSize; y++)
{
if (topleft[y] == null)
{
topleft[y] = new int[halfSize];
}
topleft[y][x] = grid[y][x];
}
}
n.topLeft = Link(topleft);
int[][] topRight = new int[halfSize][];
for (int x = halfSize; x < halfSize * 2; x++)
{
for (int y = 0; y < halfSize; y++)
{
if (topRight[y] == null)
{
topRight[y] = new int[halfSize];
}
topRight[y][x - halfSize] = grid[y][x];
}
}
n.topRight = Link(topRight);
int[][] bottomLeft = new int[halfSize][];
for (int x = 0; x < halfSize; x++)
{
for (int y = halfSize; y < halfSize * 2; y++)
{
if (bottomLeft[y - halfSize] == null)
{
bottomLeft[y - halfSize] = new int[halfSize];
}
bottomLeft[y - halfSize][x] = grid[y][x];
}
}
n.bottomLeft = Link(bottomLeft);
int[][] bottomRight = new int[halfSize][];
for (int x = halfSize; x < halfSize * 2; x++)
{
for (int y = halfSize; y < halfSize * 2; y++)
{
if (bottomRight[y - halfSize] == null)
{
bottomRight[y - halfSize] = new int[halfSize];
}
bottomRight[y - halfSize][x - halfSize] = grid[y][x];
}
}
n.bottomRight = Link(bottomRight);
if (n.topLeft == null && n.topRight == null && n.bottomLeft == null && n.bottomRight == null)
{
return null;
}
else
{
if (n.topLeft.val || n.topRight.val || n.bottomLeft.val || n.bottomRight.val)
{
n.val = true;
return n;
}
else
{
n.val = false;
return n;
}
}
}
}
