You've successfully subscribed to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 968. 监控二叉树 - Binary Tree Cameras

[DFS] [动态规划]

## solution

### My solution

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int num_Camera = 0;

public int minCameraCover(TreeNode root) {
num_Camera = 0;
if(root == null)
return 0;
if(dfs(root) == 2)
num_Camera++;
return num_Camera;
}
/*
0:  该节点已经安装了监视器
1:  该节点被监视，没有安装监视器
2： 该节点未被监视，没有安装监视器 -> 它的上一级需要安装监视器
*/
private int dfs(TreeNode node) {
if (node == null)
return 1;
int left = dfs(node.left);
int right = dfs(node.right);
/* 左右节点有一个安装监视器即可 */
if (left == 2 || right == 2) {
num_Camera++;
return 0;
} else if (left == 0 || right == 0)
return 1;
else
return 2;
}
}

### Other Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minCameraCover(TreeNode root) {
int count = order(root);
if(root==null)
return 0;
if(root.val==0)
count++;
return count;

}
private int order(TreeNode root){
if(root==null)
return 0;
int count =0;
count = order(root.left)+order(root.right);
if((root.left!=null&&root.left.val==0)||(root.right!=null&&root.right.val==0)){
root.val=2;
count++;
return count;
}
if((root.left!=null&&root.left.val==2)||(root.right!=null&&root.right.val==2)){
root.val=1;
}
return count;
}
}