Given a binary tree, we install cameras on the nodes of the tree.
Each camera at a node can monitor its parent, itself, and its immediate children.
Calculate the minimum number of cameras needed to monitor all nodes of the tree.
Example 1:
Input: [0,0,null,0,0] Output: 1 Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input: [0,0,null,0,null,0,null,null,0] Output: 2 Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.
Note:
- The number of nodes in the given tree will be in the range
[1, 1000]. - Every node has value 0.
Solution: Greedy + Recursion
Time complexity: O(n)
Space complexity: O(h)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
enum class State { NONE = 0, COVERED = 1, CAMERA = 2 }; class Solution { public: int minCameraCover(TreeNode* root) { if (dfs(root) == State::NONE) ++ans_; return ans_; } private: int ans_ = 0; State dfs(TreeNode* root) { if (!root) return State::COVERED; State l = dfs(root->left); State r = dfs(root->right); if (l == State::NONE || r == State::NONE) { ++ans_; return State::CAMERA; } if (l == State::CAMERA || r == State::CAMERA) return State::COVERED; return State::NONE; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment