https://leetcode.com/problems/quad-tree-intersection/
https://leetcode.com/problems/quad-tree-intersection/discuss/157532/Java-concise-code-beat-100
X. https://www.cnblogs.com/lz87/p/9926697.html
A quadtree is a tree data in which each internal node has exactly four children:
topLeft
, topRight
, bottomLeft
and bottomRight
. Quad trees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
We want to store True/False information in our quad tree. The quad tree is used to represent a
N * N
boolean grid. For each node, it will be subdivided into four children nodes until the values in the region it represents are all the same. Each node has another two boolean attributes : isLeaf
and val
. isLeaf
is true if and only if the node is a leaf node. The val
attribute for a leaf node contains the value of the region it represents.
For example, below are two quad trees A and B:
A: +-------+-------+ T: true | | | F: false | T | T | | | | +-------+-------+ | | | | F | F | | | | +-------+-------+ topLeft: T topRight: T bottomLeft: F bottomRight: F B: +-------+---+---+ | | F | F | | T +---+---+ | | T | T | +-------+---+---+ | | | | T | F | | | | +-------+-------+ topLeft: T topRight: topLeft: F topRight: F bottomLeft: T bottomRight: T bottomLeft: T bottomRight: F
Your task is to implement a function that will take two quadtrees and return a quadtree that represents the logical OR (or union) of the two trees.
A: B: C (A or B): +-------+-------+ +-------+---+---+ +-------+-------+ | | | | | F | F | | | | | T | T | | T +---+---+ | T | T | | | | | | T | T | | | | +-------+-------+ +-------+---+---+ +-------+-------+ | | | | | | | | | | F | F | | T | F | | T | F | | | | | | | | | | +-------+-------+ +-------+-------+ +-------+-------+
Note:
- Both
A
andB
represent grids of sizeN * N
. N
is guaranteed to be a power of 2.- If you want to know more about the quad tree, you can refer to its wiki.
- The logic OR operation is defined as this: "A or B" is true if
A is true
, or ifB is true
, or ifboth A and B are true
.
public Node intersect(Node q1, Node q2) {
if (q1.isLeaf) {
return q1.val ? q1 : q2;
}
if (q2.isLeaf) {
return q2.val ? q2 : q1;
}
q1.topLeft = intersect(q1.topLeft, q2.topLeft);
q1.topRight = intersect(q1.topRight, q2.topRight);
q1.bottomLeft = intersect(q1.bottomLeft, q2.bottomLeft);
q1.bottomRight = intersect(q1.bottomRight, q2.bottomRight);
if (q1.topLeft.isLeaf && q1.topRight.isLeaf
&& q1.bottomLeft.isLeaf && q1.bottomRight.isLeaf
&& q1.topLeft.val == q1.topRight.val
&& q1.topRight.val == q1.bottomLeft.val
&& q1.bottomLeft.val == q1.bottomRight.val) {
q1.isLeaf = true;
q1.val = q1.topLeft.val;
}
return q1;
}
X. https://www.cnblogs.com/lz87/p/9926697.html
24 public Node intersect(Node quadTree1, Node quadTree2) { 25 if(quadTree1 == null || quadTree2 == null) { 26 return null; 27 } 28 if(quadTree1.isLeaf && quadTree2.isLeaf) { 29 return new Node(quadTree1.val || quadTree2.val, true, null, null, null, null); 30 } 31 else if(quadTree1.isLeaf) { 32 return quadTree1.val ? new Node(quadTree1.val, true, null, null, null, null) 33 : new Node(quadTree2.val, quadTree2.isLeaf, quadTree2.topLeft, quadTree2.topRight, quadTree2.bottomLeft, quadTree2.bottomRight); 34 } 35 else if(quadTree2.isLeaf) { 36 return quadTree2.val ? new Node(quadTree2.val, true, null, null, null, null) 37 : new Node(quadTree1.val, quadTree1.isLeaf, quadTree1.topLeft, quadTree1.topRight, quadTree1.bottomLeft, quadTree1.bottomRight); 38 } 39 40 Node topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft); 41 Node topRight = intersect(quadTree1.topRight, quadTree2.topRight); 42 Node bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft); 43 Node bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight); 44 45 Node root = new Node(); 46 if(topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf && 47 topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) { 48 root.val = topLeft.val; 49 root.isLeaf = true; 50 } 51 else { 52 root.isLeaf = false; 53 root.topLeft = topLeft; 54 root.topRight = topRight; 55 root.bottomLeft = bottomLeft; 56 root.bottomRight = bottomRight; 57 } 58 return root; 59 }https://leetcode.com/problems/quad-tree-intersection/discuss/249072/Readable-Java-beats-100
public Node intersect(Node quadTree1, Node quadTree2) {
// Terminal condition, when any of two is leaf.
if (quadTree1.isLeaf) {
return quadTree1.val ? quadTree1 : quadTree2;
} else if (quadTree2.isLeaf) {
return quadTree2.val ? quadTree2 : quadTree1;
}
// Recurse in all 4 directions.
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);
// Detect a merger state when all 4 leaves have same value.
if (tl.isLeaf && tr.isLeaf && bl.isLeaf && br.isLeaf && tl.val == tr.val && bl.val == br.val && tl.val == bl.val) {
return new Node(tl.val, true, null, null, null, null);
} else {
return new Node(false, false, tl, tr, bl, br);
}
}