题意:给你一个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);
}
};
网友评论