package leetcode;

/**
 * https://leetcode.com/problems/quad-tree-intersection/
 */
public class Problem558 {
    private static 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;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf && quadTree2.isLeaf) {
            return new Node(quadTree1.val | quadTree2.val, true, null, null, null, null);
        } else if (!quadTree1.isLeaf && quadTree2.isLeaf) {
            boolean val = quadTree1.topLeft.val | quadTree1.topRight.val |
                quadTree1.bottomLeft.val | quadTree1.bottomRight.val;
            return new Node(val | quadTree2.val, true, null, null, null, null);
        } else if (quadTree1.isLeaf && !quadTree2.isLeaf) {
            boolean val = quadTree2.topLeft.val | quadTree2.topRight.val |
                quadTree2.bottomLeft.val | quadTree2.bottomRight.val;
            return new Node(quadTree1.val | val, true, null, null, null, null);
        }
        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);
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }

    public static void main(String[] args) {
        Problem558 prob = new Problem558();

        Node tree1 = new Node(true, false,
            new Node(true, true, null, null, null, null),
            new Node(true, true, null, null, null, null),
            new Node(false, true, null, null, null, null),
            new Node(false, true, null, null, null, null));
        Node tree2 = new Node(true, false,
            new Node(true, true, null, null, null, null),
            new Node(true, false,
                new Node(false, true, null, null, null, null),
                new Node(false, true, null, null, null, null),
                new Node(true, true, null, null, null, null),
                new Node(true, true, null, null, null, null)),
            new Node(true, true, null, null, null, null),
            new Node(false, true, null, null, null, null));

        Node tree = prob.intersect(tree1, tree2);
        System.out.println(tree.topLeft); // true
        System.out.println(tree.topRight); // true
        System.out.println(tree.bottomLeft); // true
        System.out.println(tree.bottomRight); // false
    }
}

@@ -786,101 +786,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D
 %0A   
@@ -1068,113 +1068,30 @@
     
-boolean val = quadTree1.topLeft.val %7C quadTree1.topRight.val %7C%0A                quadTree1.bottomLeft
+return quadTree2
 .val 
-%7C
+?
  qua
@@ -1099,284 +1099,117 @@
 Tree
-1.bottomRight.val;%0A            return new Node(val %7C quadTree2.val, true, null, null, null, null);%0A        %7D else if (quadTree1.isLeaf && !quadTree2.isLeaf) %7B%0A            boolean val = quadTree2.topLeft.val %7C quadTree2.topRight.val %7C%0A                quadTree2.bottomLeft
+2 : quadTree1;%0A        %7D else if (quadTree1.isLeaf && !quadTree2.isLeaf) %7B%0A            return quadTree1
 .val 
-%7C
+?
  qua
@@ -1217,105 +1217,21 @@
 Tree
-2.bottomRight.val;%0A            return new Node(quadTree1.val %7C val, true, null, null, null, null)
+1 : quadTree2
 ;%0A  
@@ -1562,686 +1562,277 @@
     
-return new Node(false, false, topLeft, topRight, bottomLeft, bottom
+if (topLeft.isLeaf && top
 Right
-);%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem558 prob = new Problem558();%0A%0A        Node tree1 = new Node(true, false,%0A            new Node(true, true, null, null, null, null),%0A            new Node(true, true, null, null, null, null),%0A            new Node(false, true, null, null, null, null),%0A            new Node(false, true, null, null, null, null));%0A        Node tree2 = new Node(true, false,%0A            new Node(true, true, null, null, null, null),%0A            new Node(true, false,%0A                new Node(false, true, null, null, null, null),%0A                new Node(false
+.isLeaf &&%0A            bottomLeft.isLeaf && bottomRight.isLeaf &&%0A            topLeft.val == topRight.val &&%0A            topLeft.val == bottomLeft.val &&%0A            topLeft.val == bottomRight.val) %7B%0A            return new Node(topLeft.val
 , tr
@@ -1854,36 +1854,34 @@
  null, null)
-,%0A  
+;%0A
         
       new No
@@ -1872,478 +1872,78 @@
     
-      new Node(true, true, null, null, null, null),%0A                new Node(true, true, null, null, null, null)),%0A            new Node(true, true, null, null, null, null),%0A            new Node(false, true, null, null, null, null));%0A%0A        Node tree = prob.intersect(tree1, tree2);%0A        System.out.println(tree.topLeft); // true%0A        System.out.println(tree.topRight); // true%0A        System.out.println(tree.bottomLeft); // true%0A        System.out.println(tree.
+%7D%0A        return new Node(true, false, topLeft, topRight, bottomLeft, 
 bott
@@ -1955,17 +1955,8 @@
 ht);
- // false
 %0A   

Solve problem 558