解决方案

方法一：动态规划

思路

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

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

算法

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

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

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

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

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

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

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

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

复杂度分析

• 时间复杂度： $$O(N)$$ ，其中 $$N$$ 是给定树中节点的数量。

• 空间复杂度： $$O(H)$$ ，其中 $$H$$ 是给定树的高度。
  
  

方法二：贪心法

思路

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

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

算法

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

复杂度分析

• 时间复杂度： $$O(N)$$ ，其中 $$N$$ 是给定树中节点的数量。

• 空间复杂度： $$O(H)$$ ，其中 $$H$$ 是给定树的高度。