四叉树,按照题目意思 递归求解即可
注意在求出node的上下左右四个子节点之后,需要判断是否可以合并成一个 leafnode
题意ref{:target=”_blank”}
C++ 代码
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
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) {
return dfs(quadTree1, quadTree2);
}
Node* dfs(Node* t1, Node* t2) {
if(!t1 || !t2)return nullptr;
if(t1->isLeaf) {
if(t1->val == 1)return t1;
else return t2;
}
if(t2->isLeaf) {
if(t2->val == 1)return t2;
else return t1;
}
Node* root = new Node();
root->topLeft = dfs(t1->topLeft, t2->topLeft);
root->topRight = dfs(t1->topRight, t2->topRight);
root->bottomLeft = dfs(t1->bottomLeft, t2->bottomLeft);
root->bottomRight = dfs(t1->bottomRight, t2->bottomRight);
if(root->topLeft->isLeaf && root->topRight->isLeaf &&
root->bottomLeft->isLeaf && root->bottomRight->isLeaf &&
root->topLeft->val == root->topRight->val &&
root->topRight->val == root->bottomLeft->val &&
root->bottomLeft->val == root->bottomRight->val) {
root->isLeaf = true;
root->val = root->topLeft->val;
root->topLeft = root->topRight = root->bottomLeft = root->bottomRight = nullptr;
}
return root;
}
};