监控二叉树 - Binary Tree Cameras

[DFS] [动态规划]

``````给定一个二叉树，我们在树的节点上安装摄像头。

``````

Example:

``````输入：[0,0,null,0,0]

``````

solution

My solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 `````` ``````/** * 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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````/** * 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; } } ``````