2019-03-27 15:39:37
问题描述:
问题求解:
很有意思的问题,问题描述简单,求解过程也可以非常的简洁,是个难得的好题。
求解的过程是自底向上进行分析,对于叶子节点,如果在叶子上放置照相机,显然是没有在其parent上放置相机来的合适的,因为叶子节点的覆盖范围没有其parent节点大。
因此,我们就可以对所有的叶子的节点的parent进行放置相机,同时将所有已经覆盖掉的节点去除掉。
对于剩下的节点重复上述的操作即可。
这里在求解的时候并不需要真实的去删除节点,只要在每个节点上加上标注信息就可以了。
叶子节点 :1
放置照相机 :2
已经被cover节点 :3
public int minCameraCover(TreeNode root) {
int[] res = new int[1];
int state = helper(root, res);
if (state == 1) res[0]++;
return res[0];
} // 1 : leaf
// 2 : camera
// 3 : covered
private int helper(TreeNode root, int[] res) {
if (root == null) return 3;
int l = helper(root.left, res);
int r = helper(root.right, res);
if (l == 3 && r == 3) return 1;
else if (l == 1 || r == 1) {
res[0]++;
return 2;
}
else return 3;
}