刷题笔记:力扣第968题-监控二叉树

1.本题是一道贪心算法问题，数据结构为二叉树。根据题意可以想到，尽可能在父节点上安装摄像头就能实现局部贪心，最终实现整体贪心。需要将每个节点分为三种状态：

（1）状态0：无覆盖，既没有摄像头也没有被别的节点监控到。

（2）状态1：有摄像头，可以监视其父节点和子节点。

（3）状态2：有覆盖，即自身没有摄像头，但已经被其父节点或子节点监控到。

2.二叉树还是需要从最底层来后续遍历，使用dfs回溯来从下往上递推。根据每个节点采集来的左右节点的状态，可以判断自身节点处于什么状态并返回给其父节点：

（1）如果左右节点状态有任何一个为0，说明当前节点必须安装摄像头来监控到子节点，返回状态1。

（2）如果左右节点状态有任何一个为1，即至少有一个摄像头，则说明当前节点能被覆盖到，不需要再安装摄像头，返回状态2。

（3）如果左右节点状态全为2，说明当前节点的最优解是被其父节点监控到，返回状态0。

（4）特殊情况，如果当前节点为空节点，说明其父节点是当前根系的最底层。空节点不能要求其父节点安装摄像头，所以返回状态2。

3.主函数的特殊情况：如果最后的根节点处的返回值为0，此时已经没有父节点来安装摄像头了，所以必须在根节点安装，摄像头数量+1。

1. /** 2. * Definition for a binary tree node. 3. * struct TreeNode { 4. * int val; 5. * struct TreeNode *left; 6. * struct TreeNode *right; 7. * }; 8. */ 9. // 返回值状态定义： 10. // 0：当前节点未被摄像头覆盖，需要父节点安装摄像头 11. // 1：当前节点安装了摄像头，可以覆盖父、子节点 12. // 2：当前节点无摄像头，但已被子节点摄像头覆盖 13. int dfs(struct TreeNode* node, int* cameras){ 14. // 空节点视作已经被覆盖，返回2 15. if (!node) return 2; 16. 17. // 后序遍历，先处理左右子树 18. int l = dfs(node->left, cameras); 19. int r = dfs(node->right, cameras); 20. 21. // 左/右孩子有未被覆盖(0)，当前节点必须装摄像头 22. if (l == 0 || r == 0){ 23. (*cameras)++; 24. return 1; 25. } 26. 27. // 左/右孩子装有摄像头(1)，当前节点被覆盖，无需装摄像头 28. if (l == 1 || r == 1){ 29. return 2; 30. } 31. 32. // 左右都被覆盖(2)，当前节点暂时无摄像头，等待父节点覆盖自己 33. if (l == 2 && r == 2){ 34. return 0; 35. } 36. 37. return -1; 38. } 39. 40. int minCameraCover(struct TreeNode* root) { 41. int cameras = 0; 42. int rootStatus = dfs(root, &cameras); 43. // 根节点返回0：根没有父节点，必须额外装一个摄像头 44. if (rootStatus == 0) { 45. cameras++; 46. } 47. 48. return cameras; 49. }

该算法时间复杂度和空间复杂度均为O(n)（n为树中节点的数量）。