Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/558.html
558. Quad Tree Intersection (Easy)
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
.
Solution 1.
-
/* // 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 { 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 root = 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); if (topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val && topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf) { root.val = topLeft.val; root.isLeaf = true; } else { root.topLeft = topLeft; root.topRight = topRight; root.bottomLeft = bottomLeft; root.bottomRight = bottomRight; } return root; } } } ############ /* // 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 { public Node intersect(Node quadTree1, Node quadTree2) { return dfs(quadTree1, quadTree2); } private Node dfs(Node t1, Node t2) { if (t1.isLeaf && t2.isLeaf) { return new Node(t1.val || t2.val, true); } if (t1.isLeaf) { return t1.val ? t1 : t2; } if (t2.isLeaf) { return t2.val ? t2 : t1; } Node res = new Node(); res.topLeft = dfs(t1.topLeft, t2.topLeft); res.topRight = dfs(t1.topRight, t2.topRight); res.bottomLeft = dfs(t1.bottomLeft, t2.bottomLeft); res.bottomRight = dfs(t1.bottomRight, t2.bottomRight); boolean isLeaf = res.topLeft.isLeaf && res.topRight.isLeaf && res.bottomLeft.isLeaf && res.bottomRight.isLeaf; boolean sameVal = res.topLeft.val == res.topRight.val && res.topRight.val == res.bottomLeft.val && res.bottomLeft.val == res.bottomRight.val; if (isLeaf && sameVal) { res = res.topLeft; } return res; } }
-
// OJ: https://leetcode.com/problems/quad-tree-intersection/ // Time: O(logN) // Space: O(logN) class Solution { public: Node* intersect(Node* quadTree1, Node* quadTree2) { if (quadTree1->isLeaf) return quadTree1->val ? quadTree1 : quadTree2; if (quadTree2->isLeaf) return quadTree2->val ? quadTree2 : quadTree1; auto tl = intersect(quadTree1->topLeft, quadTree2->topLeft); auto tr = intersect(quadTree1->topRight, quadTree2->topRight); auto bl = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft); auto br = intersect(quadTree1->bottomRight, quadTree2->bottomRight); int val = tl->val; if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf && val == tr->val && val == bl->val && val == br->val) { delete tl; delete tr; delete bl; delete br; return new Node(val, true, NULL, NULL, NULL, NULL); } return new Node(false, false, tl, tr, bl, br); } };
-
""" # Definition for a QuadTree node. class Node: def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight): self.val = val self.isLeaf = isLeaf self.topLeft = topLeft self.topRight = topRight self.bottomLeft = bottomLeft self.bottomRight = bottomRight """ class Solution: def intersect(self, quadTree1: "Node", quadTree2: "Node") -> "Node": def dfs(t1, t2): if t1.isLeaf and t2.isLeaf: return Node(t1.val or t2.val, True) if t1.isLeaf: return t1 if t1.val else t2 if t2.isLeaf: return t2 if t2.val else t1 res = Node() res.topLeft = dfs(t1.topLeft, t2.topLeft) res.topRight = dfs(t1.topRight, t2.topRight) res.bottomLeft = dfs(t1.bottomLeft, t2.bottomLeft) res.bottomRight = dfs(t1.bottomRight, t2.bottomRight) isLeaf = ( res.topLeft.isLeaf and res.topRight.isLeaf and res.bottomLeft.isLeaf and res.bottomRight.isLeaf ) sameVal = ( res.topLeft.val == res.topRight.val == res.bottomLeft.val == res.bottomRight.val ) if isLeaf and sameVal: res = res.topLeft return res return dfs(quadTree1, quadTree2) ############ """ # Definition for a QuadTree node. class Node(object): def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight): self.val = val self.isLeaf = isLeaf self.topLeft = topLeft self.topRight = topRight self.bottomLeft = bottomLeft self.bottomRight = bottomRight """ class Solution(object): def intersect(self, q1, q2): """ :type q1: Node :type q2: Node :rtype: Node """ if q1.isLeaf: return q1 if q1.val else q2 if q2.isLeaf: return q2 if q2.val else q1 q1.topLeft = self.intersect(q1.topLeft, q2.topLeft) q1.topRight = self.intersect(q1.topRight, q2.topRight) q1.bottomLeft = self.intersect(q1.bottomLeft, q2.bottomLeft) q1.bottomRight = self.intersect(q1.bottomRight, q2.bottomRight) if q1.topLeft.isLeaf and q1.topRight.isLeaf and q1.bottomLeft.isLeaf and q1.bottomRight.isLeaf: if q1.topLeft.val == q1.topRight.val == q1.bottomLeft.val == q1.bottomRight.val: q1.isLeaf = True q1.val = q1.topLeft.val return q1
-
/** * Definition for a QuadTree node. * type Node struct { * Val bool * IsLeaf bool * TopLeft *Node * TopRight *Node * BottomLeft *Node * BottomRight *Node * } */ func intersect(quadTree1 *Node, quadTree2 *Node) *Node { var dfs func(*Node, *Node) *Node dfs = func(t1, t2 *Node) *Node { if t1.IsLeaf && t2.IsLeaf { return &Node{Val: t1.Val || t2.Val, IsLeaf: true} } if t1.IsLeaf { if t1.Val { return t1 } return t2 } if t2.IsLeaf { if t2.Val { return t2 } return t1 } res := &Node{} res.TopLeft = dfs(t1.TopLeft, t2.TopLeft) res.TopRight = dfs(t1.TopRight, t2.TopRight) res.BottomLeft = dfs(t1.BottomLeft, t2.BottomLeft) res.BottomRight = dfs(t1.BottomRight, t2.BottomRight) isLeaf := res.TopLeft.IsLeaf && res.TopRight.IsLeaf && res.BottomLeft.IsLeaf && res.BottomRight.IsLeaf sameVal := res.TopLeft.Val == res.TopRight.Val && res.TopRight.Val == res.BottomLeft.Val && res.BottomLeft.Val == res.BottomRight.Val if isLeaf && sameVal { res = res.TopLeft } return res } return dfs(quadTree1, quadTree2) }