968 Binary Tree Cameras 监控二叉树
Description:
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:
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
题目描述:
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 :
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示:
给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。
思路:
后序遍历
每一个结点有 3 种状态:
0 表示该结点安装了监视器
1 表示该结点可被监视器观察到且没有安装监视器
2 表示该结点没被监视器观察到
空结点则认为该结点状态为 1, 也没办法装监视器
如果左结点或者右结点有没被观测到的结点, 需要在根结点装一个监视器, 并将根结点的值返回为 0
如果左结点或者右结点已经有监视器, 直接返回 1, 表示根结点能被监测到而且不用装监视器
安装完毕之后, 整棵树的根结点有可能没被检测到, 需要单独装一个监视器
时间复杂度为 O(2 ^ n), 空间复杂度为 O(2 ^ n)
代码:
C++:
/**
* 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
{
private:
int result;
int dfs(TreeNode* root)
{
if (!root) return 1;
int left = dfs(root -> left), right = dfs(root -> right);
if (left == 2 or right == 2)
{
++result;
return 0;
}
else if (!left or !right) return 1;
return 2;
}
public:
int minCameraCover(TreeNode* root)
{
result = 0;
if (dfs(root) == 2) ++result;
return result;
}
};
Java:
class Solution {
private int result = 0;
public int minCameraCover(TreeNode root) {
result = 0;
if (dfs(root) == 2) ++result;
return result;
}
private int dfs(TreeNode root) {
if (root == null) return 1;
int left = dfs(root.left), right = dfs(root.right);
if (left == 2 || right == 2) {
++result;
return 0;
} else if (left == 0 || right == 0) return 1;
return 2;
}
}
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
self.result = 0
def dfs(root: TreeNode) -> int:
if not root:
return 1
left, right = dfs(root.left), dfs(root.right)
if left == 2 or right == 2:
self.result += 1
return 0
elif not left or not right:
return 1
return 2
if dfs(root) == 2:
self.result += 1
return self.result
