LeetCode 558. Intersection of quadtree

558. The intersection of quadtrees

【 Divide and conquer + recursive 】 This question is too long , But we can simply sort it out ：

1. If either of the two nodes is a leaf ：

        If the leaf is 1, Then directly return to 1 Just leave it

        If the leaf is 0, Then directly return to another node

2. Recursive processing of four children , Get four recursive results respectively

        If all four are leaves ,

                If it's all 1, Returns a merged large 1 node

                If it's all 0, Returns a merged large 0 node

        otherwise , Return to create a large node based on four recursive nodes

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() {}

    public Node(boolean _val,boolean _isLeaf,Node _topLeft,Node _topRight,Node _bottomLeft,Node _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {

    // 4.12 16

    public Node dfs(Node n1, Node n2) {
        Node node = new Node();
        if (n1.isLeaf) {
            if (n1.val == true) return new Node(true, true, null, null, null, null);
            else return n2;
        } 
        if (n2.isLeaf) {
            if (n2.val == true) return new Node(true, true, null, null, null, null);
            else return n1;
        }
        Node tl = dfs(n1.topLeft, n2.topLeft);
        Node tr = dfs(n1.topRight, n2.topRight);
        Node bl = dfs(n1.bottomLeft, n2.bottomLeft);
        Node br = dfs(n1.bottomRight, n2.bottomRight);
        if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf) {
            if (tl.val && tr.val && bl.val && br.val) {
                return new Node(true, true, null, null, null, null);
            }
            if (tl.val == false && tr.val == false && bl.val == false && br.val == false) {
                return new Node(false, true, null, null, null, null);
            }
        }
        return new Node(false, false, tl, tr, bl, br);
    }

    public Node intersect(Node quadTree1, Node quadTree2) {
        return dfs(quadTree1, quadTree2);
    }
}