Force deduction solution summary 558- intersection of quadtrees

Directory links ：

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

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

All elements in the binary matrix are not 0 Namely 1 .

Here are two quadtrees for you ,quadTree1 and quadTree2. among quadTree1 It means a n * n Binary matrix , and quadTree2 Represents another n * n Binary matrix .

Please return a representation n * n Quadtree of binary matrix , It is quadTree1 and quadTree2 Represented by two binary matrices Bitwise logical or operation Result .

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 ：quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]
, quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Output ：[[0,0],[1,1],[1,1],[1,1],[1,0]]
explain ：quadTree1 and quadTree2 As shown above . Binary matrices represented by quadtrees have also been given .
If we perform bitwise logical or operations on these two matrices , Then you can get the following binary matrix , Represented by a resulting quadtree .
Be careful , The binary matrix we show is only to better illustrate the meaning of the problem , You don't need to construct a binary matrix to get the resulting quadtree .

Example 2：

Input ：quadTree1 = [[1,0]]
, quadTree2 = [[1,0]]
Output ：[[1,0]]
explain ： The matrix size represented by both numbers is 1*1, It's worth it all 0 
The resulting matrix size is 1*1, It's worth it all 0 .
Example 3：

Input ：quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]
Output ：[[1,1]]
Example 4：

Input ：quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
Output ：[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]
Example 5：

Input ：quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
, quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]
Output ：[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]
 

Tips ：

quadTree1 and quadTree2 They are all quadtrees that meet the requirements of the topic , Each represents a n * n Matrix .
n == 2^x , among 0 <= x <= 9.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/logical-or-of-two-binary-grids-represented-as-quad-trees
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  A recursive problem , If either of the two nodes isLeaf by true, If val=1 Use itself , Otherwise, use another . because 1|0 perhaps 1|1 All for 1. and 0 Is the input value .
*  If there are two nodes isLeaf All for false, Then recursively judge , Modify the returned node after the result is obtained isLeaf and val.
*  What we should pay attention to here is , To judge whether the four values are consistent, it should be a==b&b==c&c==d, instead of a==b==c==d. I checked this problem for more than three hours 

Code ：

public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf) {
            if (quadTree1.val) {
                return quadTree1;
            }
            return quadTree2;
        }
        if (quadTree2.isLeaf) {
            if (quadTree2.val) {
                return quadTree2;
            }
            return quadTree1;
        }
        Node node = new Node();
        node.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
        node.topRight = intersect(quadTree1.topRight, quadTree2.topRight);
        node.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
        node.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
        // Are they all consistent 
        node.isLeaf = (node.topLeft.isLeaf & node.topRight.isLeaf & node.bottomRight.isLeaf & node.bottomLeft.isLeaf) && (node.topLeft.val == node.topRight.val) &&  (node.topRight.val == node.bottomLeft.val)&&  (node.bottomLeft.val == node.bottomRight.val);
        node.val = node.topLeft.val | node.topRight.val | node.bottomRight.val | node.bottomLeft.val;
        if (node.isLeaf) {
            node.topLeft = null;
            node.topRight = null;
            node.bottomRight = null;
            node.bottomLeft = null;
        }
        return node;
    }