树上dp

#数据结构#算法

二叉树树上dp+状态机 力扣相关题目(监控二叉树)

该题分为三种状态：

  • dp[root]表示以root为根的子树需要多少个监控
  • dp[root][0]：root由自己监控
  • dp[root][1]：root由儿子监控
  • dp[root][2]：root由父亲监控

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int>dfs(TreeNode* root){
        if(!root){
            return {(int)1e9,0,0};
        }
        vector<int>v(3);
        //v[0]靠自己监控，v[1]靠儿子监控，v[2]靠父亲监控
        vector<int>l=dfs(root->left);
        vector<int>r=dfs(root->right);
        v[0]=1+min(l[2],l[0])+min(r[2],r[0]);
        v[1]=min({l[0]+r[0],l[0]+r[1],r[0]+l[1]});
        v[2]=min(l[0],l[1])+min(r[0],r[1]);
        return v;
    }
    int minCameraCover(TreeNode* root) {
        vector<int>v=dfs(root);
        return min(v[0],v[1]);
    }
};

联系方式 - 如果你 喜欢 我的话~

GitHubbilibiliCSDN

ZHM