LeetCode/src/easy/QuadTreeIntersection.java at master · chenyiAlone/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package easy;

/**
 * ClassName: QuadTreeIntersection.java
 * Author: chenyiAlone
 * Create Time: 2019/12/5 16:03
 * Description: No.558 QuadTree Intersection
 */
public class QuadTreeIntersection {

    public Node intersect(Node quadTree1, Node quadTree2) {
        if (quadTree1.isLeaf)
            return quadTree1.val ? quadTree1 : quadTree2;
        else if (quadTree2.isLeaf)
            return quadTree2.val ? quadTree2 : quadTree1;
        else {
            Node tl = intersect(quadTree1.topLeft, quadTree2.topLeft);
            Node tr = intersect(quadTree1.topRight, quadTree2.topRight);
            Node bl = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
            Node br = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
            if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf && tl.val == tr.val && tr.val == bl.val && bl.val == br.val)
                return tl;
            return new Node(false, false, tl, tr, bl, br);
        }
    }

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

}