Leetcode-968.监控二叉树

思路

类似一个树形DP，考虑如何从左右儿子更新父亲的状态即可，一共有三个状态

0 ： 没被覆盖

1： 放置摄像机

2： 没放置摄像机被覆盖

然后每个节点有八个状态自己总结就可以了

代码实现

class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {
        if(cur==NULL)return 2;
        int left = traversal(cur->left);
        int right = traversal(cur->right);
        if(left == 2 && right == 2){
            return 0;
        }
        else if(left == 0 || right == 0){
            result++;
            return 1;
        }else if(left == 1 || right == 1){
            return 2;
        }
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};