558.四叉树交集

链接：558.四叉树交集
难度：Medium
标签：树、分治
简介：请你返回一个表示 n * n 二进制矩阵的四叉树，它是 quadTree1 和 quadTree2 所表示的两个二进制矩阵进行 按位逻辑或运算 的结果。

题解 1 - cpp

• 编辑时间：2022-07-15
• 执行用时：24ms
• 内存消耗：16.2MB
• 编程语言：cpp
• 解法介绍：分治,如果一个叶子且 true,则与该节点相同,如果 false,则与另一个节点相同,否则递归。

class Solution {
   public:
    Node *intersect(Node *quadTree1, Node *quadTree2) {
        if (quadTree1->isLeaf) {
            if (quadTree1->val)
                return new Node(true, true);
            else
                return new Node(quadTree2->val, quadTree2->isLeaf,
                                quadTree2->topLeft, quadTree2->topRight,
                                quadTree2->bottomLeft, quadTree2->bottomRight);
        }
        if (quadTree2->isLeaf) {
            if (quadTree2->val)
                return new Node(true, true);
            else
                return new Node(true, false, quadTree1->topLeft,
                                quadTree1->topRight, quadTree1->bottomLeft,
                                quadTree1->bottomRight);
        }
        Node *tl = intersect(quadTree1->topLeft, quadTree2->topLeft),
             *tr = intersect(quadTree1->topRight, quadTree2->topRight),
             *bl = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft),
             *br = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
        if (tl->isLeaf && tr->isLeaf && bl->isLeaf && br->isLeaf &&
            tl->val == tr->val && tl->val == bl->val && tl->val == br->val)
            return new Node(tl->val, true);
        else
            return new Node(false, false, tl, tr, bl, br);
    }
};