From 185ef9fcb0e59f13e9ee0ccb261693cdaddebab0 Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Tue, 23 Feb 2021 21:07:19 +0800
Subject: import(solutions): Move leetcode solutions to subdir.

---
 works/solutions/leetcode/cpp/968.cpp | 63 ++++++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)
 create mode 100644 works/solutions/leetcode/cpp/968.cpp

(limited to 'works/solutions/leetcode/cpp/968.cpp')

diff --git a/works/solutions/leetcode/cpp/968.cpp b/works/solutions/leetcode/cpp/968.cpp
new file mode 100644
index 0000000..c9e6b24
--- /dev/null
+++ b/works/solutions/leetcode/cpp/968.cpp
@@ -0,0 +1,63 @@
+#include <cstddef>
+
+struct TreeNode
+{
+    int val;
+    TreeNode *left;
+    TreeNode *right;
+    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
+};
+
+#include <algorithm>
+
+struct Result
+{
+    // root_camera >= root_monitored >= root_not_monitored
+    int root_camera;
+    int root_monitored;
+    int root_not_monitored;
+};
+
+class Solution
+{
+public:
+    Result dfs(TreeNode *root)
+    {
+        if (root->left == nullptr && root->right == nullptr)
+        {
+            return Result{1, 1, 0};
+        }
+
+        if (root->left == nullptr || root->right == nullptr)
+        {
+            TreeNode *child_node = root->left == nullptr ? root->right : root->left;
+            Result child = dfs(child_node);
+
+            int root_camera = 1 + child.root_not_monitored;
+            int root_monitored = std::min({child.root_camera,
+                                           root_camera});
+            int root_not_monitored = std::min(child.root_monitored, root_monitored);
+
+            return Result{
+                root_camera, root_monitored, root_not_monitored};
+        }
+
+        Result left = dfs(root->left);
+        Result right = dfs(root->right);
+
+        int root_camera = 1 + left.root_not_monitored + right.root_not_monitored;
+        int root_monitored = std::min({left.root_camera + right.root_monitored,
+                                       left.root_monitored + right.root_camera,
+                                       root_camera});
+        int root_not_monitored = std::min({left.root_monitored + right.root_monitored, root_monitored});
+
+        return Result{
+            root_camera, root_monitored, root_not_monitored};
+    }
+
+    int minCameraCover(TreeNode *root)
+    {
+        auto result = dfs(root);
+        return result.root_monitored;
+    }
+};
\ No newline at end of file
-- 
cgit v1.2.3