LeetCode 558. 四叉树交集（递归）
LeetCode 558. 四叉树交集（递归）
Michael阿明
发布于 2020-07-13 16:05:57
发布于 2020-07-13 16:05:57
1. 题目
四叉树是一种树数据，其中每个结点恰好有四个子结点：topLeft、topRight、bottomLeft 和 bottomRight。四叉树通常被用来划分一个二维空间，递归地将其细分为四个象限或区域。
我们希望在四叉树中存储 True/False 信息。四叉树用来表示 N * N 的布尔网格。对于每个结点, 它将被等分成四个孩子结点直到这个区域内的值都是相同的。每个节点都有另外两个布尔属性：isLeaf 和 val。当这个节点是一个叶子结点时 isLeaf 为真。val 变量储存叶子结点所代表的区域的值。
例如，下面是两个四叉树 A 和 B：
A:
+-------+-------+ T: true
| | | F: false
| T | T |
| | |
+-------+-------+
| | |
| F | F |
| | |
+-------+-------+
topLeft: T
topRight: T
bottomLeft: F
bottomRight: F
B:
+-------+---+---+
| | F | F |
| T +---+---+
| | T | T |
+-------+---+---+
| | |
| T | F |
| | |
+-------+-------+
topLeft: T
topRight:
topLeft: F
topRight: F
bottomLeft: T
bottomRight: T
bottomLeft: T
bottomRight: F你的任务是实现一个函数，该函数根据两个四叉树返回表示这两个四叉树的逻辑或(或并)的四叉树。
A: B: C (A or B):
+-------+-------+ +-------+---+---+ +-------+-------+
| | | | | F | F | | | |
| T | T | | T +---+---+ | T | T |
| | | | | T | T | | | |
+-------+-------+ +-------+---+---+ +-------+-------+
| | | | | | | | |
| F | F | | T | F | | T | F |
| | | | | | | | |
+-------+-------+ +-------+-------+ +-------+-------+提示： A 和 B 都表示大小为 N * N 的网格。 N 将确保是 2 的整次幂。 逻辑或的定义如下：如果 A 为 True ，或者 B 为 True ，或者 A 和 B 都为 True，则 “A 或 B” 为 True。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/quad-tree-intersection 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
/*
// 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* q1, Node* q2) {
if(q1->isLeaf || q2->isLeaf)//至少有一个是叶子(全0 or 全1)
{
if(q1->isLeaf && q2->isLeaf)//都是叶子
{
bool v = q1->val || q2->val;//求并
return new Node(v,true,0,0,0,0);
}
else if(q1->isLeaf)
{
if(q1->val == false)//q1全为0，并集由q2决定
return q2;
else
return q1;//q1全为1，直接返回q1
}
else//q2->isLeaf
{
if(q2->val == false)//q2全为0，并集由q1决定
return q1;
else
return q2;//q2全为1，直接返回q2
}
}
else//q1,q2都不是叶子，其下面有true，有false
{
Node *root = new Node(false,false,0,0,0,0);
root->topLeft = intersect(q1->topLeft, q2->topLeft);
root->topRight = intersect(q1->topRight, q2->topRight);
root->bottomLeft = intersect(q1->bottomLeft, q2->bottomLeft);
root->bottomRight = intersect(q1->bottomRight, q2->bottomRight);
if(root->topLeft->isLeaf && root->topRight->isLeaf
&& root->bottomLeft->isLeaf && root->bottomRight->isLeaf)
{ //四个子节点都是叶子
bool topL = root->topLeft->val;
if(root->topRight->val == topL && root->bottomLeft->val == topL
&& root->bottomRight->val == topL)
{ //且四个子节点的值都相同，则root是叶子
root->isLeaf = true;
root->val = topL;
//舍弃孩子(合并了)
root->topLeft = root->topRight = root->bottomLeft
= root->bottomRight = NULL;
}
}
return root;
}
}
};
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-11-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录