0558 solved.

liuyubobobo · liuyubobobo · commit 0b4fb495f7f4 · 2022-07-14T14:11:54.000-07:00
diff --git a/0501-1000/0558-Logical-OR-of-Two-Binary-Grids-Represented-as-Quad-Trees/cpp-0558/CMakeLists.txt b/0501-1000/0558-Logical-OR-of-Two-Binary-Grids-Represented-as-Quad-Trees/cpp-0558/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0558)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0558 main.cpp)
diff --git a/0501-1000/0558-Logical-OR-of-Two-Binary-Grids-Represented-as-Quad-Trees/cpp-0558/main.cpp b/0501-1000/0558-Logical-OR-of-Two-Binary-Grids-Represented-as-Quad-Trees/cpp-0558/main.cpp
@@ -0,0 +1,94 @@
+/// Source : https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/
+/// Author : liuyubobobo
+/// Time   : 2022-07-14
+
+#include <iostream>
+
+using namespace std;
+
+
+/// DFS
+/// Time Complexity: O(n)
+/// Space Complexity: O(h)
+
+/// 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);
+    }
+
+private:
+    Node* dfs(Node* node1, Node* node2){
+
+        if(node1->isLeaf && node2->isLeaf){
+            return new Node(node1->val | node2->val, true);
+        }
+
+        Node* ret = new Node(0, false);
+        ret->topLeft = dfs(node1->topLeft ? node1->topLeft : new Node(node1->val, true),
+                           node2->topLeft ? node2->topLeft : new Node(node2->val, true));
+        ret->topRight = dfs(node1->topRight ? node1->topRight : new Node(node1->val, true),
+                            node2->topRight ? node2->topRight : new Node(node2->val, true));
+        ret->bottomLeft = dfs(node1->bottomLeft ? node1->bottomLeft : new Node(node1->val, true),
+                              node2->bottomLeft ? node2->bottomLeft : new Node(node2->val, true));
+        ret->bottomRight = dfs(node1->bottomRight ? node1->bottomRight : new Node(node1->val, true),
+                               node2->bottomRight ? node2->bottomRight : new Node(node2->val, true));
+
+        if(ret->topLeft->isLeaf && ret->topRight->isLeaf && ret->bottomLeft->isLeaf && ret->bottomRight->isLeaf &&
+           same(ret->topLeft->val, ret->topRight->val, ret->bottomLeft->val, ret->bottomRight->val)){
+            ret->val = ret->topLeft->val;
+            ret->isLeaf = true;
+            ret->topLeft = ret->topRight = ret->bottomLeft = ret->bottomRight = nullptr;
+        }
+        return ret;
+    }
+
+    bool same(bool a, bool b, bool c, bool d){
+        return a == b && a == c && a == d;
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -585,7 +585,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | | | | | | |
 | 556 | [Next Greater Element III](https://leetcode.com/problems/next-greater-element-iii/) | [solution](https://leetcode.com/problems/next-greater-element-iii/solution/)<br/>[缺：底层实现] | [C++](0501-1000/0556-Next-Greater-Element-III/cpp-0556/) | | |
 | 557 | [Reverse Words in a String III](https://leetcode.com/problems/reverse-words-in-a-string-iii/description/) | [solution](https://leetcode.com/problems/reverse-words-in-a-string-iii/solution/) | [C++](0501-1000/0557-Reverse-Words-in-a-String-III/cpp-0557/) | | |
-| | | | | | |
+| 558 | [Logical OR of Two Binary Grids Represented as Quad-Trees](https://leetcode.com/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/) | [无] | [C++](0501-1000/0558-Logical-OR-of-Two-Binary-Grids-Represented-as-Quad-Trees/cpp-0558/) | | |
 | 559 | [Maximum Depth of N-ary Tree](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/description/) | [solution](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/solution/) | [C++](0501-1000/0559-Maximum-Depth-of-N-ary-Tree/cpp-0559/) | | |
 | 560 | [Subarray Sum Equals K](https://leetcode.com/problems/subarray-sum-equals-k/) | [solution](https://leetcode.com/problems/subarray-sum-equals-k/solution/) | [C++](0501-1000/0560-Subarray-Sum-Equals-K/cpp-0560/) | | |
 | 561 | [Array Partition I](https://leetcode.com/problems/array-partition-i/description/) | [solution](https://leetcode.com/problems/array-partition-i/solution/) | [C++](0501-1000/0561-Array-Partition-I/cpp-0561/) | | |
