558. Logical OR of Two Binary Grids Represented as Quad-Trees

Time: O(n)

Space: O(log n)

Intuition

Recursively OR two quad-tree nodes. If either is a leaf of 1, result is 1. If both are leaves of 0, result is 0. Otherwise recurse on all four quadrants.

Algorithm

1If n1 is leaf with val=1 or n2 is leaf with val=1: return leaf(1).
2If n1 is leaf with val=0: return n2. If n2 is leaf with val=0: return n1.
3Recurse on TL, TR, BL, BR.
4If all four children are leaves with same val: collapse to a single leaf.

Common Pitfalls

•After recursing, check if all four children are uniform leaves to compress the tree.

558.cs

// Approach: Recursively merge two quad-trees. If either is an all-true leaf
// the result is immediately true; otherwise merge all four quadrants.
// Time: O(n) Space: O(log n)

// Definition for a QuadTree node.
public class Node
{
    public bool val;
    public bool isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    public Node() { }
    public Node(bool _val, bool _isLeaf, Node _topLeft, Node _topRight, Node _bottomLeft, Node _bottomRight)
    {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
}

public 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 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 &&
            topLeft.val == bottomLeft.val &&
            topLeft.val == bottomRight.val &&
            topLeft.isLeaf && topRight.isLeaf &&
            bottomLeft.isLeaf && bottomRight.isLeaf)
            return new Node(topLeft.val, true);
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
}

Was this solution helpful?