解决方案


方法一:动态规划

思路

让我们在给定的树中尝试自顶向下地监控每一个节点。每一个节点必须被它自身或者它邻居节点上的某个摄像头监控。

由于摄像头的安放只关心当前节点的状态,我们希望能够利用这一个事实来构建一个高效的解法。具体来说就是,当决定是否要在某个节点上放置摄像头的时候,我们只需要关心当前节点所在的子树内它本身、它的左孩子和右孩子被监控的状态就可以了。

算法

我们定义 solve(node) 表示 node 处于不同状态时,监控以它为根的子树内其他所有节点需要使用的摄像头的数量。一共有三种本质不同的状态:

  • 【状态 0】准监控子树:子树内除了根节点,其他节点都被摄像头监控了。

  • 【状态 1】完全监控子树:子树内的所有节点都被摄像头监控了,但是根节点上并未放置摄像头。

  • 【状态 2】 已放置摄像头的子树:子树内的所有节点都被摄像头监控了,并且根节点上放置了一个摄像头(可以用于监控此节点在原树中的父亲节点)。

一旦我们以这种方式构建问题,那么答案就呼之欲出了:

  • 为了能够监控一颗 准监控子树,根节点的每一个子节点必须处于状态 1。

  • 为了能够监控一颗 完全监控子树 ,我们不在根节点放置摄像头,但要保证根节点的子节点必须处于状态 1 或状态 2,同时至少有一个子节点处于状态 2。

  • 为了能够监控一颗 已放置摄像头的子树,我们在根节点放置一个摄像头,而根节点的子节点可以处于三种状态的任何一种。

复杂度分析

  • 时间复杂度:,其中 是给定树中节点的数量。

  • 空间复杂度:,其中 是给定树的高度。


方法二:贪心法

思路

除了由上向下的尝试监控树中的每一个节点,我们还可以试着自下向上的考虑这个问题 —— 先使用摄像头将树中最深的节点监控起来,然后按这种方式在树中向上重复处理。

如果一个节点的子节点都已经被监控了,并且它还有一个父节点,那么将摄像头安放在这个节点的父节点上一定更优。

算法

如果一个节点存在子节点没有被摄像头监控,那么我们一定要在这个节点上放置一个摄像头。另外,如果一个节点没有父节点并且它还没有被监控,那么我们也要在这个节点上放置一个摄像头。

复杂度分析

  • 时间复杂度:,其中 是给定树中节点的数量。

  • 空间复杂度:,其中 是给定树的高度。