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为树中节点的数量。