diff options
| author | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
|---|---|---|
| committer | Yuqian Yang <crupest@crupest.life> | 2025-02-28 23:13:39 +0800 |
| commit | dc1f0c4c0096013799416664894c5194dc7e1f52 (patch) | |
| tree | 2f5d235f778cd720f4c39ec3e56b77ba6d99f375 /store/works/solutions/leetcode/cpp/968.cpp | |
| parent | 7299d424d90b1effb6db69e3476ddd5af72eeba4 (diff) | |
| download | crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.gz crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.tar.bz2 crupest-dc1f0c4c0096013799416664894c5194dc7e1f52.zip | |
chore(store): move everything to store.
Diffstat (limited to 'store/works/solutions/leetcode/cpp/968.cpp')
| -rw-r--r-- | store/works/solutions/leetcode/cpp/968.cpp | 63 |
1 files changed, 63 insertions, 0 deletions
diff --git a/store/works/solutions/leetcode/cpp/968.cpp b/store/works/solutions/leetcode/cpp/968.cpp new file mode 100644 index 0000000..c9e6b24 --- /dev/null +++ b/store/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 |