Abstract#动态规划#树状DP#贪心策略1. 题目题目LeetCode 968. 监控二叉树核心思路每个摄像头可以覆盖自身、父节点和直接子节点。为了最小化摄像头数量采用贪心策略自底向上遍历。每个节点有3种状态0无覆盖、1有覆盖无摄像头、2有覆盖有摄像头。空节点统一返回状态1。对于非空节点如果其任一子节点处于无覆盖则该节点必须放置摄像头如果任一子节点有摄像头则该节点被覆盖按照贪心策略无需再放置摄像头否则左右子节点均为有覆盖无摄像头状态该节点处于无覆盖状态0。按照策略将状态逐层向上传递。复杂度时间复杂度O ( n ) O(n)O(n)空间复杂度O ( h e i g h t ) O(height)O(height)。2. 代码classSolution{public:intans;intstate(TreeNode*x){if(xnullptr)return1;intleftstate(x-left);intrightstate(x-right);if(left0||right0){ans;return2;}if(left1right1)return0;return1;}intminCameraCover(TreeNode*root){ans0;intfinalStatestate(root);if(finalState0)ans;returnans;}};3. 心得复盘思路这道题目的转移情况我独立想出来了尽管没有意识到是贪心的思想但是在实现方式上却禁锢在之前树状DP问题的状态传递方式了。更精确地说我被局限在“放与不放”这个二元的状态中但此题因为摄像头覆盖规则复杂仅靠二元状态无法表达节点被谁覆盖的情况父节点、子节点还是自身必须区分“有覆盖无摄像头”和“有覆盖有摄像头”因此加上“无覆盖”需要3个状态。既然已经从状态入手了结合贪心的策略只有存在无覆盖子结点的时候才要放置答案才需要加一可以知道我们需要传递的只是状态根据状态我们就可以判断是否在总答案中加一。Special Case空结点不需要被监控视为“有覆盖无摄像头”。这样叶子节点的左右子节点状态均为1叶子节点自身状态就为0触发父节点放置摄像头。如果若根节点返回状态0证明根节点还未被其子结点覆盖需在根节点额外放置一个摄像头。4. 相关题目Luogu P2458 保安站岗