简述网站建设基本步骤,炫酷的动画网站,wordpress 登录页美化,微型营销网站制作监控二叉树
Leetcode 968
学习记录自代码随想录
给定一个二叉树#xff0c;我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。
要点#xff1a;1.想到优先覆盖叶子节点#xff0c…监控二叉树
Leetcode 968
学习记录自代码随想录
给定一个二叉树我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。
要点1.想到优先覆盖叶子节点即让叶子节点的父节点有摄像头 2.想到每个节点有三种状态0-无覆盖1-摄像头2-有覆盖 3.优先覆盖叶子节点需要从下到上遍历用后序遍历左右中 4.四种情况a.左右节点都有覆盖则中间节点为无覆盖b.左右节点至少一个无覆盖则中间节点为摄像头1c.左右节点至少一个摄像头则中间节点为有覆盖d.最后判断根节点是否为无覆盖若是还要添加一个摄像头到根节点 5.首先是要想到贪心的思路然后就是遍历和状态推导此题较难很难直接想到。
/*** 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:int result;int traversal(TreeNode* cur){//节点状态0-无覆盖1-摄像头2-有覆盖// 空节点为有覆盖2, 因为尽量保证叶子节点的父节点有摄像头所以空节点只能为有覆盖2if(cur nullptr) return 2;// 尽量保证叶子节点被覆盖即叶子节点父节点要有摄像头所以遍历为后序遍历int left traversal(cur-left);int right traversal(cur-right);// 1.左右节点均为有覆盖2则中间节点为无覆盖0if(left 2 right 2) return 0;// 2.左右节点至少一个为无覆盖0则中间节点为摄像头1if(left 0 || right 0){result;return 1;}// 3.左右节点至少一个有摄像头则中间节点为有覆盖2if(left 1 || right 1) return 2;return -1; // 上述代码未使用else所以逻辑不会走到这里仅作形式此处}int minCameraCover(TreeNode* root) {// 局部最优让叶子节点的父节点安摄像头所用摄像头最少整体最优全部摄像头数量所用最少result 0;// 4.如果最后根节点无覆盖则需要多一个摄像头if(traversal(root) 0){result;}return result;}
};
