Problem: 968. 监控二叉树
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
使用动态规划的方法来解决这个问题。从叶子节点开始向上递归,对于每个节点,我们可以考虑三种状态:当前节点没有摄像头,但它的子节点已经全部被覆盖。当前节点有摄像头。当前节点没有被任何摄像头覆盖。对于这三种状态,我们可以用0、1、2分别表示上述三种情况,其中:
0 表示当前节点没有被任何摄像头覆盖。
1 表示当前节点没有摄像头,但它的子节点已经全部被覆盖。
2 表示当前节点有摄像头。
当递归到根节点时,如果根节点没有被任何摄像头覆盖(即状态为0),则需要额外添加一个摄像头。
解题方法
使用后序遍历的方式进行递归处理。对于每个节点,先递归处理左右子树,然后根据左右子树的状态确定当前节点的状态,并更新总的摄像头数量。
复杂度
时间复杂度:
O ( n ) O(n) O(n),其中n是二叉树的节点数。每个节点被访问一次。
空间复杂度:
O ( h ) O(h) O(h),其中h是二叉树的高度。递归调用栈深度与树的高度成正比,在最坏情况下,二叉树退化为链状结构,空间复杂度退化为 O ( n ) O(n) O(n)。
Code
class Solution {
public int ans = 0;
public int minCameraCover(TreeNode root) {
if(f(root) == 0) {
ans++;
}
return ans;
}
public int f(TreeNode x) {
if(x == null) {
return 1;
}
int left = f(x.left);
int right = f(x.right);
if(left == 0 || right == 0) {
ans++;
return 2;
}
if(left == 1 && right == 1) {
return 0;
}
return 1;
}
}