Summary of force deduction solution 427- establishment of quadtree

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

GitHub - September26/java-algorithms: Algorithm problem summary , Including Niuke ,leetCode,lintCode The solution and code of website problems , And complete mode class , There are even code generation tools for linked lists .

Original link ： Power button

describe ：

To give you one n * n matrix grid , The matrix consists of several 0 and 1 form . Please use a quadtree to represent the matrix grid .

You need to return something that represents a matrix quadtree Root node of .

Be careful , When isLeaf by False when , You can take True perhaps False Assign to node , Both values will be judged by the problem determination mechanism Accept .

Quadtree data structure , Each internal node has only four child nodes . Besides , Each node has two properties ：

val： Store the value of the area represented by the leaf node .1 Corresponding True,0 Corresponding False;
isLeaf: When this node is a leaf node, it is True, If it has 4 The child nodes are False .
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}
We can build a quadtree for a two-dimensional region as follows ：

If the values of the current grid are the same （ namely , All for 0 Or all 1）, take isLeaf Set to True , take val Set to the corresponding value of the grid , And set all four child nodes to Null Then stop .
If the value of the current grid is different , take isLeaf Set to False, take val Set to any value , Then as shown in the figure below , Divides the current mesh into four sub meshes .
Recurse each child node using the appropriate sub mesh .

If you want to know more about quadtrees , You can refer to wiki .

Quadtree format ：

The output is the serialized form of quadtree after sequence traversal , among null Indicates the path terminator , There is no node below it .

It is very similar to the serialization of binary trees . The only difference is that nodes are represented in a list [isLeaf, val] .

If isLeaf perhaps val The value of is True , It is in the list  [isLeaf, val] The value of 1 ; If isLeaf perhaps val The value of is False , Then the value is 0 .

Example 1：

Input ：grid = [[0,1],[1,0]]
Output ：[[0,1],[1,0],[1,1],[1,1],[1,0]]
explain ： The explanation of this example is as follows ：
Please note that , In the diagram of the quadtree below ,0 Express false,1 Express True .

Example 2：

Input ：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]]
Output ：[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
explain ： All values in the grid are different . We divide the grid into four sub grids .
topLeft,bottomLeft and bottomRight All have the same value .
topRight Have different values , So we subdivide it into 4 Sub grid , In this way, each sub grid has the same value .
The explanation is shown in the figure below ：

Example 3：

Input ：grid = [[1,1],[1,1]]
Output ：[[1,1]]
Example 4：

Input ：grid = [[0]]
Output ：[[1,0]]
Example 5：

Input ：grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output ：[[0,1],[1,1],[1,0],[1,0],[1,1]]
 

Tips ：

n == grid.length == grid[i].length
n == 2^x among 0 <= x <= 6

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/construct-quad-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  Construct a recursive method , The input parameters are array and range .
*  In this recursive method , If the values are all the same , Returns a Node Node isLeaf=true.
*  Otherwise, call recursively four times , Find the upper left , The upper right , The lower left , Four ranges on the lower right Node value .

Code ：

public class Solution427 {

    public Node construct(int[][] grid) {
        Node construct = construct(grid, 0, grid[0].length, 0, grid.length);
        return construct;
    }

    public Node construct(int[][] grid, int startX, int endX, int startY, int endY) {

        // Whether the values are the same 
        boolean isEqual = true;
        int value = -1;
        flag:
        for (int y = startY; y < endY; y++) {
            for (int x = startX; x < endX; x++) {
                if (value == -1) {
                    value = grid[y][x];
                    continue;
                }
                if (value == grid[y][x]) {
                    continue;
                }
                isEqual = false;
                break flag;
            }
        }
        Node node = new Node();
        if (isEqual) {
            node.val = value == 1;
            node.isLeaf = true;
            return node;
        }
        node.val = false;
        node.isLeaf = false;
        int middleX = startX + (endX - startX) / 2;
        int mideleY = startY + (endY - startY) / 2;
        node.topLeft = construct(grid, startX, middleX, startY, mideleY);
        node.topRight = construct(grid, middleX, endX, startY, mideleY);
        node.bottomLeft = construct(grid, startX, middleX, mideleY, endY);
        node.bottomRight = construct(grid, middleX, endX, mideleY, endY);

        return node;
    }

    static 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;
        }
    }
}