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

题目信息

题号:

0558

难度:

Medium

主题:

四叉树、二进制网格、逐格逻辑或、结构压缩

原题:

LeetCode 0558

重点:

两棵树表示同尺寸网格、结果按逐格 OR 定义、叶节点表示整块同值区域、可合并四个相同叶子

题目重述

给定两棵四叉树 quadTree1 和 quadTree2,它们分别表示两个尺寸相同的二进制方阵。叶节点的 val 表示其覆盖区域全部为 0 或全部为 1,非叶节点通过四个子节点表示四个象限。

对两个原始网格的对应位置执行逻辑或,构造并返回结果网格的四叉树。若某个区域的所有格子在结果中相同,可以用一个叶节点表示;四个子区域都成为相同值叶节点时,允许合并为一个叶节点。

自建示例

一个网格整块为 1:

输入:quadTree1 是 val=true 的叶节点,quadTree2 表示任意同尺寸网格
输出:val=true 的叶节点
解释:1 与任意二进制值执行逻辑或都得到 1,因此整个结果区域均为 1。

一个网格整块为 0:

输入:quadTree1 是 val=false 的叶节点,quadTree2 表示另一网格
输出:与 quadTree2 表示相同网格的四叉树
解释:0 与另一格值执行逻辑或后保持另一格值不变。

叶节点短路,递归合并四个象限

若任一输入区域是值为 1 的叶节点,整个结果区域必为 1;若一方是值为 0 的叶节点,结果直接等于另一方。只有两方都非叶时才递归计算四个象限,随后检查四个结果是否都是相同值的叶节点,若是则压缩回一个叶节点。

C++ 实现

class Solution {
public:
    Node* intersect(Node* first, Node* second) {
        if (first->isLeaf) {
            return first->val ? new Node(true, true) : second;
        }
        if (second->isLeaf) {
            return second->val ? new Node(true, true) : first;
        }

        Node* result = new Node(false, false);
        result->topLeft = intersect(first->topLeft, second->topLeft);
        result->topRight = intersect(first->topRight, second->topRight);
        result->bottomLeft = intersect(first->bottomLeft,
                                       second->bottomLeft);
        result->bottomRight = intersect(first->bottomRight,
                                        second->bottomRight);

        Node* children[4] = {
            result->topLeft, result->topRight,
            result->bottomLeft, result->bottomRight
        };
        bool merge = true;
        for (int i = 0; i < 4; ++i) {
            if (!children[i]->isLeaf ||
                children[i]->val != children[0]->val) {
                merge = false;
                break;
            }
        }
        if (merge) {
            return new Node(children[0]->val, true);
        }
        return result;
    }
};

代码分析

叶节点规则直接对应区域逐格 OR 的恒等关系,非叶区域递归覆盖四个互不重叠象限;四叶合并保持表示的语义不变并压缩结构。每对对应节点最多处理一次,时间复杂度为 O(q),额外递归空间为 O(h),其中 q 为两树展开后的对应节点规模。