【动态规划】【树形dp】【C++算法】968监控二叉树

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

LeetCode:968监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
示例 2：
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
给定树的节点数的范围是 [1, 1000]。
每个节点的值都是 0。

动态规划

动态规划的状态表示

Rec(root)返回int i1,i2,i3，表示后面三种情况需要的最少摄像头。 i1，表示此子树根节点有摄像头，且子树所有节点都被监控。i2，此子树根节没有摄像头，所有节点都被监控。i3，此子树根节点无摄像头，根节点无监控，除根节点外都被监控。

动态规划的转移方程

叶子节点见初始值，本部分只讨论，非叶子节点：
i3 = min(lefti2)+min(righti2)
i2 ,左节点i1，右节点i1或i2 。或右节点i1，左节点i1,i2不存在。如果右节点不存在，则左节点i1。如果左节点不存在，则右节点i1。
i1 1 + min(lefti1,lefti2,lefti3)+min(righti1,righti2,righti3)
如果当前节点增加摄像头，则左右子树，无轮是否存在，i1,i2,i3 全部是i1。
如果当前节点没摄像头
a，一个子树i1，另外一个子树i1,i2或不存在，都是i2。
b，一个字树i1，另外一个字树i3不合法。
c，没有子树i1。两者都i2。就是i3。

动态规划的初始值

叶子节点i1,i2,i3分别为：1, 1000,0 。 1000或更大的数，表示这种可能不存在。

动态规划的填表顺序

树的先序遍历

动态规划的返回值

root的i1。

代码

核心代码

class Solution {public:int minCameraCover(TreeNode* root) {const auto [i1,i2,i3] =Rec(root);return max(1, min(i1, i2));}std::tuple<int, int,int> Rec(TreeNode* root){if ((nullptr == root->left) && (nullptr == root->right)){return std::make_tuple(1, 1000, 0);}int i3 = 0;int i21 = 1000,i22=1000;int i1 = 1;//int iLeftMin = -1, iRightMin = -1;if (nullptr != root->left){auto [t1, t2,t3] = Rec(root->left);iLeftMin = min(t1, t2);i3 += t2;i21 = t1;i1 += min(t1, min(t2, t3));}if (nullptr != root->right){auto [t1, t2, t3] = Rec(root->right);iRightMin = min(t1, t2);i3 += t2;i22 = t1;i1 += min(t1,min(t2, t3));}if (nullptr != root->left){i22 += iLeftMin;}if (nullptr != root->right){i21 += iRightMin;}const int i2 = min(i21, i22);//assert((i1 >= i3) && (i2 >= i3 ));std::cout << "val: " << root->val << " i1: " << i1 << " i2:" << i2 << " i3: " << i3 << std::endl;return std::make_tuple(i1, i2,i3);}};

测试用例

template<class T>void Assert(const T& t1, const T& t2){assert(t1 == t2);}template<class T>void Assert(const vector<T>& v1, const vector<T>& v2){if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main(){int x,target;const int null = 10000;{vector<int> nodes = { 1, null, 3, null, 5, null, 7, null, 9, 10, 11, null, null, 14, 15 };auto root = NTree::Init(nodes);Solution sln;auto res = sln.minCameraCover(root);Assert(res, 3);}{vector<int> nodes = { 1, 2, null, 4, null, 6, null, null, 9 };auto root = NTree::Init(nodes);Solution sln;auto res = sln.minCameraCover(root);Assert(res, 2);}{vector<int> nodes = { 1, 2, null, 3, 4 };auto root = NTree::Init(nodes);Solution sln;auto res = sln.minCameraCover(root);Assert(res, 1);}}

优化

空节点为边界条件，更简洁。

class Solution {public:int minCameraCover(TreeNode* root) {const auto [i1,i2,i3] =Rec(root);return max(1, min(i1, i2));}std::tuple<int, int,int> Rec(TreeNode* root){if (nullptr == root ){return std::make_tuple(1000,0,0);}auto [l1,l2,l3] = Rec(root->left);auto [r1, r2, r3] = Rec(root->right);int i1 = 1 + min(min(l1,l2),l3) + min(min(r1, r2), r3);int i2 = min(l1 + r2, r1 + l2);i2 = min(i2, l1 + r1);int i3 = l2 + r2;return std::make_tuple(i1, i2,i3);}};

2023年1月版

struct CStatus
{
int m_iFillAndRootHas;// 覆盖所有节点且根节点有监控
int m_iFill;// 覆盖所有节点，根节点不一定有监控
int m_iFillChild;//覆盖子节点，不一定覆盖根节点
};
class Solution {
public:
int minCameraCover(TreeNode* root) {
CStatus stuatu = dfs(root);
return stuatu.m_iFill;
}
CStatus dfs(TreeNode* root)
{
if (nullptr == root)
{
return{ INT_MAX / 2, 0, 0 };
}
CStatus left = dfs(root->left);
CStatus right = dfs(root->right);
CStatus ret;
ret.m_iFillAndRootHas = 1 + left.m_iFillChild + right.m_iFillChild;
ret.m_iFill = min(ret.m_iFillAndRootHas, min(left.m_iFillAndRootHas+right.m_iFill,right.m_iFillAndRootHas+left.m_iFill));
ret.m_iFillChild = min(ret.m_iFillAndRootHas,left.m_iFill + right.m_iFill);
std::cout << ret.m_iFillAndRootHas << " " << ret.m_iFill << " " << ret.m_iFillChild << std::endl;
return ret;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。