Logical OR of Two Binary Grids Represented as Quad-Trees — LeetCode 558 Python Solution
MediumTreeDivide and Conquer
- Problem
- #558
- Pattern
- Tree Traversal
- Reading time
- 8 min
- Source
- leetcode.com
The problem
A Binary Matrix is a matrix in which all the elements are either 0 or 1. Given quadTree1 and quadTree2.
Example
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}Python solution
Python
"""
# 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)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(h) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees?
- LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees is rated Medium on LeetCode.
- What is the time complexity of LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees?
- The Python solution on this page uses O(h) auxiliary space.
- What topics does LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees cover?
- LeetCode 558. Logical OR of Two Binary Grids Represented as Quad-Trees is tagged Tree and Divide and Conquer on LeetCode.