监控二叉树详细讲解

女爷i 2023-02-10 13:28 34阅读 0赞

## 一、前言 ##

问题来源LeetCode 968，难度：困难

问题链接：[https://leetcode-cn.com/problems/binary-tree-cameras/][https_leetcode-cn.com_problems_binary-tree-cameras]

## 二、题目 ##

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

**示例 1：**

![20200521002645516.png][]

输入：[0,0,null,0,0]
    输出：1
    解释：如图所示，一台摄像头足以监控所有节点。

**示例 2：**

![20200521002727789.png][]

输入：[0,0,null,0,null,0,null,null,0]
    输出：2
    解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

##  ##

## 三、分析 ##

不要被题意中的二叉树限制了思维。我们将其看成图或者网状结构，从整体分析这个问题，树给人的感觉往往是从上往下分析。这道题我们需要从下往上分析。叶子结点父节点放置摄像头覆盖的结点最多——要想叶子结点被覆盖，摄像头要不放在叶子结点，要不放在叶子结点父结点，放在父节点覆盖的结点会更多。宗旨：摄像头放置叶子结点父节点上，去掉已经被覆盖的结点，继续这个操作。

### 3.1 从简单入手，逐渐添加结点： ###

图1：要满足两个叶子结点被监视到摄像头放在6

![20200521002818727.png][]

图2：4 和 7 是叶子结点摄像头放置他们父节点上 2 和 6

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

图3：原理同图2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

图4：原理同时

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2][]

###  ###

### 3.2 简单原理分析完我们看一个完整实例 ###

图5： 叶子结点有 4、3、5、8，先忘记这是一颗二叉树，把它当着网状结构。从最底层叶子结点开始，最底层叶子结点是3、5、8，摄像头需要放置 4和9这两个结点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3][]

图6：摄像头放置在4和9位置。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4][]

图7：已经被覆盖的点，不需要在考虑了，可以去掉，看着更加清晰。结点2由于还有一个子结点，不能去掉，它对它的左结点还存在影响。剩下 4 2 6将摄像头放置2即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5][]

图8：完整放置展示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6][]

##  ##

## 四、思路 ##

上面分析我们可以得出，放置最少的摄像头，覆盖所有的点。现在我们怎样将其为代码实现呢？

图9：一个节点有三种状态：无覆盖（0）、被覆盖（1）、摄像头（2）、待确定（为父结点状态，是通过子结点推导出来的）

![2020052100332157.png][]

我们是通过子结点来推导出父结点。需要特殊说明一下，一个父结点可能只有一个子结点，我们可以用被覆盖状态的结点来代替它另外一个子结点，前文图7，已经说明。

子结点状态可能组合 （0，0）、（0，1）、（0，2），（1，1）、（1，2），（2，2），一共有6个类型，不用考虑左右结点顺序，不影响父结点状态。

图10：（0，0）、（0，1）、（0，2） 待确定结点状态需要设置成 状态2（摄像头）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7][]

图11：（1，1） 待确定结点需要设置成 状态0（无覆盖）。它的两个子结点都为1，被覆盖状态的节点是可以直接去掉，即当前的父节点可以看成一个叶子节点，如果它有父节点则它的父节点会被设置成摄像头（状态2），如果没有那它是一个根节点我们需要将其设置成摄像头（状态2）。这个结点是觉得它父结点状态。

![20200521003433333.png][]

图12：（1，2），（2，2）待确定结点的子结点有摄像头，它的状态需要设置成状态1（被覆盖状态）

![20200521003521973.png][]

以上我们已经通过子结点可以推导出父节点状态了。万事俱备只欠编码了。

## 五、编码实现 ##

//==========================================================================
    /**
    * @file : MinCameraCover.h
    * @title : 监控二叉树
    * @purpose : 给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量
    *
    示例 1：
    *        0
    *       /
    *      0(摄像头) 
    *	  / \
    *    0   0
    * 输入：[0,0,null,0,0]
    * 输出：1
    * 解释：如图所示，一台摄像头足以监控所有节点。
    
    * 示例 2：
    *			0
    *		   /	
    *		  0(摄像头) 
    *		 /
    *       0
    *      /
    *     0(摄像头)  
    *      \
    *       0
    * 输入：[0,0,null,0,null,0,null,null,0]
    * 输出：2
    * 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
    
    * 提示：
    * 给定树的节点数的范围是 [1, 1000]。
    * 每个节点的值都是 0。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-cameras
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    *
    */
    //==========================================================================
    #pragma once
    #include "Common.h"
    #include "ConstructTree.h"
    
    template<class T>
    int minCameraCover(BinaryTreeNode<T>* root)
    {
    	if (root == nullptr) return 0;
    	int ans = 0;
    	if (minCameraCover_DFS(root, ans) == 0) ans++;   // 返回状态0，为什么需要+1，见图11
    	return ans;
    }
    
    template<class T>
    int minCameraCover_DFS(BinaryTreeNode<T>* node, int& ans)
    {
    	if (node == nullptr)
    		return 1;
    
    	int left = minCameraCover_DFS(node->m_pLeft, ans);
    	int right = minCameraCover_DFS(node->m_pRight, ans);
    
    	if (left == 0 || right == 0) // 见图10分析
    	{
    		ans++;
    		return 2;
    	}
    	else if (left == 1 && right == 1) // 见图11分析
    	{
    		return 0;
    	}
    	else // 见图12分析
    	{
    		return 1;
    	}
    }
    
    
    // 以下为测试代码
    #define NAMESPACE_MINCAMERACOVER namespace NAME_MINCAMERACOVER {
    #define NAMESPACE_MINCAMERACOVEREND }
    
    //
    // 测试 用例 START
    NAMESPACE_MINCAMERACOVER
    
    template<class T>
    void test(const char* testName, BinaryTreeNode<T>* root, int expect)
    {
    	int sum = minCameraCover(root);
    	if (sum == expect)
    	{
    		cout << testName << " solution passed." << endl;
    	}
    	else
    	{
    		cout << testName << " solution failed. sum: " << sum << endl;
    	}
    }
    
    // 根结点
    //        2        
    void Test1()
    {
    	const int length = 1;
    	int preorder[length] = { 2 };
    	int inorder[length] = { 2 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 1;
    
    	test("Test1()", pRoot, expect);
    }
    
    // 完全二叉树
    //             2
    //           /   \
    //          1     3  
    void Test2()
    {
    	const int length = 3;
    	int preorder[length] = { 2, 1, 3 };
    	int inorder[length] = { 1, 2, 3 };
    
    	BinaryTreeNode<int>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 1;
    
    	test("Test2()", pRoot, expect);
    }
    
    // 普通二叉树
    //              1
    //           /     \
    //          2       3  
    //         /       / \
    //        4       5   6
    //         \         /
    //          7       8
    void Test3()
    {
    	const int length = 8;
    	char preorder[length + 1] = "12473568";
    	char inorder[length + 1] = "47215386";
    
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 3;
    
    	test("Test3()", pRoot, expect);
    }
    
    // 普通二叉树
    //                a
    //            /       \
    //           b         c  
    //         /   \      / \
    //        d     e    f   g
    //             / \     
    //            h   i  
    void Test4()
    {
    	const int length = 9;
    	char preorder[length + 1] = "abdehicfg";
    	char inorder[length + 1] = "dbheiafcg";
    	
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 3;
    
    	test("Test4()", pRoot, expect);
    }
    
    // 所有结点都没有右子结点
    //            1
    //           / 
    //          2   
    //         / 
    //        3 
    //       /
    //      4
    //     /
    //    5
    void Test5()
    {
    	const int length = 5;
    	char preorder[length + 1] = "12345";
    	char inorder[length + 1] = "54321";
    	
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 2;
    
    	test("Test5()", pRoot, expect);
    }
    
    // 所有结点都没有左子结点
    //            1
    //             \ 
    //              2   
    //               \ 
    //                3 
    //                 \
    //                  4
    //                   \
    //                    5
    void Test6()
    {
    	const int length = 5;
    	char preorder[length + 1] = "12345";
    	char inorder[length + 1] = "12345";
    
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 2;
    
    	test("Test6()", pRoot, expect);
    }
    
    // 完全二叉树
    //              1
    //           /     \
    //          2       3  
    //         / \     / \
    //        4   5   6   7
    void Test7()
    {
    	const int length = 7;
    	char preorder[length+1] = "1245367";
    	char inorder[length+1] = "4251637";
    
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 2;
    
    	test("Test7()", pRoot, expect);
    }
    
    // 完全二叉树
    //             4
    //           /    \
    //          2      5  
    //         / \    
    //        1   3   
    void Test8()
    {
    	const int length = 5;
    	char preorder[length + 1] = "42135";
    	char inorder[length + 1] = "12345";
    
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 2;
    
    	test("Test8()", pRoot, expect);
    }
    
    // 二叉树
    //              6
    //           /    \
    //          2      7  
    //         / \      \ 
    //        1   4      9
    //           / \    / 
    //          3   5  8  
    void Test9()
    {
    	const int length = 9;
    	char preorder[length + 1] = "621435798";
    	char inorder[length + 1] = "123456789";
    	
    	BinaryTreeNode<char>* pRoot = ConstructTree(preorder, inorder, length);
    	int expect = 3;
    
    	test("Test9()", pRoot, expect);
    }
    
    
    NAMESPACE_MINCAMERACOVEREND
    // 测试 用例 END
    //
    
    void MinCameraCover_Test()
    {
    	NAME_MINCAMERACOVER::Test1();
    	NAME_MINCAMERACOVER::Test2();
    	NAME_MINCAMERACOVER::Test3();
    	NAME_MINCAMERACOVER::Test4();
    	NAME_MINCAMERACOVER::Test5();
    	NAME_MINCAMERACOVER::Test6();
    	NAME_MINCAMERACOVER::Test7();
    	NAME_MINCAMERACOVER::Test8();
    	NAME_MINCAMERACOVER::Test9();
    }

**执行结果：**

![20200521003654487.png][]

[https_leetcode-cn.com_problems_binary-tree-cameras]: https://leetcode-cn.com/problems/binary-tree-cameras/
[20200521002645516.png]: https://img-blog.csdnimg.cn/20200521002645516.png
[20200521002727789.png]: https://img-blog.csdnimg.cn/20200521002727789.png
[20200521002818727.png]: https://img-blog.csdnimg.cn/20200521002818727.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200521002844948.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200521002904719.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020052100293120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200521003057372.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020052100312174.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200521003144881.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200521003235276.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[2020052100332157.png]: https://img-blog.csdnimg.cn/2020052100332157.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200521003358181.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200521003433333.png]: https://img-blog.csdnimg.cn/20200521003433333.png
[20200521003521973.png]: https://img-blog.csdnimg.cn/20200521003521973.png
[20200521003654487.png]: https://img-blog.csdnimg.cn/20200521003654487.png