美文网首页LeetCode蹂躏集
2018-09-11 558. Quad Tree Inters

2018-09-11 558. Quad Tree Inters

作者: alexsssu | 来源:发表于2018-09-11 09:08 被阅读0次

    题意:给你一个Quad Tree概念,然后给两个Quad Tree,求这两个Quad Tree的或(OR)
    解题思路:或的基本概念是一真即真,全假即假。
    注意事项:
    第一、A真返回A;B真返回B;A假返回B;B假返回A;
    第二、不能直接比较两个空指针NULL,或含有空指针成员的结构体,因为任意两个空指针NULL都不相等。
    第三、如果需要使用递归返回值,需要用临时变量接住再使用,可以减少递归次数。

    /*
    // Definition for a QuadTree node.
    class Node {
    public:
        bool val;
        bool isLeaf;
        Node* topLeft;
        Node* topRight;
        Node* bottomLeft;
        Node* bottomRight;
    
        Node() {}
    
        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;
        }
    };
    */
    class Solution {
    public:
        Node* intersect(Node* quadTree1, Node* quadTree2) {
            if(quadTree1->isLeaf && quadTree1->val) return quadTree1;
            if(quadTree2->isLeaf && quadTree2->val) return quadTree2;
            if(quadTree1->isLeaf && !quadTree1->val) return quadTree2;
            if(quadTree2->isLeaf && !quadTree2->val) return quadTree1;
            Node* q1 = intersect(quadTree1->topLeft, quadTree2->topLeft);
            Node* q2 = intersect(quadTree1->topRight, quadTree2->topRight);
            Node* q3 = intersect(quadTree1->bottomLeft, quadTree2->bottomLeft);
            Node* q4 = intersect(quadTree1->bottomRight, quadTree2->bottomRight);
            if(q1->val == q2->val && q1->val == q3->val && q1->val == q4->val && q1->isLeaf && q2->isLeaf && q3->isLeaf && q4->isLeaf)
                return new Node(q1->val, true, NULL, NULL, NULL, NULL);
            return new Node(false, false, q1, q2, q3, q4);
        }
    };
    

    相关文章

      网友评论

        本文标题:2018-09-11 558. Quad Tree Inters

        本文链接:https://www.haomeiwen.com/subject/skeygftx.html