diff options
author | crupest <crupest@outlook.com> | 2021-02-23 21:07:19 +0800 |
---|---|---|
committer | crupest <crupest@outlook.com> | 2021-02-23 21:07:19 +0800 |
commit | d8f3b40085619cb680c8f227c65a1f5acc393223 (patch) | |
tree | 6a38e3a6c79276fc396259ef962d17236dbed569 /cpp/968.cpp | |
parent | b0162802ad9723c678e495f29ca2f0fc0af2eff1 (diff) | |
download | solutions-d8f3b40085619cb680c8f227c65a1f5acc393223.tar.gz solutions-d8f3b40085619cb680c8f227c65a1f5acc393223.tar.bz2 solutions-d8f3b40085619cb680c8f227c65a1f5acc393223.zip |
Move leetcode solutions to subdir.
Diffstat (limited to 'cpp/968.cpp')
-rw-r--r-- | cpp/968.cpp | 63 |
1 files changed, 0 insertions, 63 deletions
diff --git a/cpp/968.cpp b/cpp/968.cpp deleted file mode 100644 index 4feecf6..0000000 --- a/cpp/968.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#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 |