一、题目
You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
Example 1:
Input: root = [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.
Example 2:
Input: root = [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.
Constraints:
The number of nodes in the tree is in the range [1, 1000].
Node.val == 0
二、题解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = 0;
/*
三种状态
0-无覆盖
1-有摄像头
2-有覆盖
*/
int traversal(TreeNode* cur){
//空节点：默认有覆盖
if(cur == nullptr) return 2;
int left = traversal(cur->left);
int right = traversal(cur->right);
//左右节点均有覆盖
if(left == 2 && right == 2) return 0;
//左节点无覆盖或右节点无覆盖
if(left == 0 || right == 0){
res++;
return 1;
}
//左右节点中至少一个有摄像头
if(left == 1 || right == 1) return 2;
return -1;
}
int minCameraCover(TreeNode* root) {
//如果根节点无覆盖
if(traversal(root) == 0) res++;
return res;
}
};
