LeetCode 558: Logical OR of Two Binary Grids Represented as Quad-Trees
Problem Description
Explanation
To solve this problem, we need to perform a logical OR operation on two quad-trees. We can recursively traverse the quad-trees and perform logical OR operation on corresponding nodes. We have the following cases:
- If both nodes are leaf nodes, perform logical OR on their values.
- If one node is a leaf node and the other is not, set the result to be the non-leaf node.
- If both nodes are non-leaf nodes, recursively process their children.
We can define a recursive function intersect that takes two nodes as input and returns the resulting node after performing logical OR operation. The base cases are when either one of the nodes is a leaf or both are leaf nodes.
Time complexity: O(n), where n is the number of nodes in the quad-trees. Space complexity: O(log n) due to the recursive stack.
Solutions
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;
}
Node result = new Node();
result.topLeft = intersect(quadTree1.topLeft, quadTree2.topLeft);
result.topRight = intersect(quadTree1.topRight, quadTree2.topRight);
result.bottomLeft = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
result.bottomRight = intersect(quadTree1.bottomRight, quadTree2.bottomRight);
if (result.topLeft.isLeaf && result.topRight.isLeaf
&& result.bottomLeft.isLeaf && result.bottomRight.isLeaf
&& result.topLeft.val == result.topRight.val
&& result.topRight.val == result.bottomLeft.val
&& result.bottomLeft.val == result.bottomRight.val) {
result.isLeaf = true;
result.val = result.topLeft.val;
result.topLeft = null;
result.topRight = null;
result.bottomLeft = null;
result.bottomRight = null;
}
return result;
}
}Related LeetCode Problems
Loading editor...