968. 监控二叉树
968. 监控二叉树 给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。 示例 1： 输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。 示例 2： 输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。 提示： 给定树的节点数的范围是 [1, 1000]。 每个节点的值都是 0。 java代码 这是一道hard难度的题目。我们要从底向上进行推导，因为尽量让叶子节点的父节点安装摄像头，这样摄像头的数量才是最少的。 如何从低向上推导呢？ 采用后序遍历也就是左右中的顺序，这样就可以从下到上进行推导了。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //NO_CAMERA表示的是子节点没有相机，当前节点也没放相机 private final int NO_CAMERA = 0; //HAS_CAMERA表示当前节点有一个相机 private final int HAS_CAMERA = 1; //NO_NEEDED表示当前节点没有相机，但他的子节点有一个相机，把它给 //覆盖了，所以它不需要了。或者他是一个空的节点也是不需要相机的 private final int NO_NEEDED = 2; //全局的，统计有多少相机 int res = 0; public int minCameraCover(TreeNode root) { //边界条件判断 if (root == null) return 0; //如果最后返回的是NO_CAMERA，表示root节点的子节点也没有相机， //所以root节点要添加一个相机 if (dfs(root) == NO_CAMERA) res++; //返回结果 return res; } public int dfs(TreeNode root) { //如果是空的，就不需要相机了 if (root == null) return NO_NEEDED; int left = dfs(root....